New answers tagged primes
0
votes
Is Determining the Number of distinct Prime Factors Polynomial?
It’s easy to find small prime factors. Pollard-rho can find a factor p in $O(\sqrt p)$ which finds many prime factors. And for large n with no known small prime factors we can do a primality test ...
- 28.4k
2
votes
Testing whether a number (N) is prime or not can be made very fast but it will require storage space
It would be pointless. A well implemented sieve can find prime numbers much faster than you could ever download them.
Now creating a sieve storing a large number of primes will make trial division ...
- 28.4k
1
vote
Testing whether a number (N) is prime or not can be made very fast but it will require storage space
Your algorithm is no good. It is not feasible to store all the prime numbers, or all prime numbers of a reasonable size (e.g., 1024 bits). That would require more storage than there are atoms in the ...
D.W.♦
- 156k
Top 50 recent answers are included