I pass this problem with Sieve of Eratosthenes, but i think solution with Pollard's rho algorithm is funnier, and wrote it too.

If you cant pass it with this algo just use all prime modules from 1'000'000'007 to 1'000'001'393.

Test 47 is some number from 1e14 to 1e18 with correct answer "No".

Please add the following testcase:

869637034218881024 = 2^18 * 1806487 * 1836383

The answer should be "Yes". My solution prints "No" and nevertheless has AC.

Check 524288, should be NO.
Test other cases where you have 19 factors, and the last one remaining is 1.

who has ideas, what test it is?

Help please:
Test 23, whats wrong, what test should chek?

def sieve(n):
    lis = list(range(n + 1))
    lis[1] = 0
    for i in lis:
        if i > 1:
            for j in range(i + i, len(lis), i):
                lis[j] = 0
    return [i for i in lis if i != 0]
c = sieve(200)
a = int(input())
if a == 0:
    print('No')
i = 0
b = []
e = 0
while a != 1:
    if a%5 != 0 and a%2 != 0 and a%3 != 0:
        e +=1
        break

    elif a % c[i] == 0:
        a /= c[i]
        b.append(c[i])
        continue

    else:
        i += 1
d = str(len(b))
if  len (b) == 20 or (len (b) == 19 and e != 0):
    print('Yes')
else:
    print('No')

Не подскажете 38-тест?

24303989349327424 = 2^6 * 11^14 (Yes)
79792266297612001 = 7^20 (Yes)
467851794974552912 = 7^1 * 2^4 * 11^15 (Yes)
566608619280937216 = 2^8 * 19^12 (Yes)
932195579567617600 = 5^2 * 2^6 * 17^12 (Yes)
999983616067108864 = 1953109^2 * 2^18 (Yes)
999197664639844352 = 19681^3 * 2^17 (Yes)
998848442311376896 = 15619^3 * 2^18 (No)
999999999987679232 = 1907348632789^1 * 2^19 (Yes)
798352691495399040 = 2^7 * 3^1 * 5^1 * 7^1 * 11^1 * 13^1 * 17^1 * 19^1 * 23^1 * 29^1 * 31^1 * 37^1 * 41^2 (Yes)

I thought that using the sieve of Eratosthenes would slow down the program, but it turned out the opposite.

Edited by author 05.11.2020 03:23

Edited by author 05.11.2020 03:23

Edited by author 05.11.2020 03:23

What is test 23?

Edited by author 29.05.2020 13:26

Edited by author 29.05.2020 13:26

i got TLE 21

I get TLE on 22 test. What can you advise?

Can someone provide a test, that makes the following code get TLE?

// ITNOA
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll n;
    cin >> n;
    int cnt = 0;
    for (ll i = 2;i*i <= min((ll)1e18, n);i++)
        while (n%i == 0)
        {
            n /= i;
            cnt++;
        }
    if (n > 1)
        cnt++;
    if (cnt == 20)
        cout << "Yes\n";
    else
        cout << "No\n";
}

2^19 or another where factorized number = 19

0.436 seconds, 6840 kb
just go to google and type there:
monte carlo factorization
---
this algo is O(N^1/4), so its O(1e4 * sqrt(2))

Please help me. TLE #39

1) Find the prime numbers up to 10,000,100 (Sieve of Eratosthenes)
2) if the sum is equal to 19 degrees, then the residue is prime to check
What can you advise?