|
|
|
|
|
|
by kadoban
1595 days ago
|
|
|
Yes. Very few (no?) primality tests require knowing or learning all primes up to the number being tested. Even trial division (the most simplistic test), you can stop looking for potential divisors once you pass sqrt(n), you learn nothing about most numbers up to n. |
|
|
If you do trial division in increasing order, you’ll find one (the smallest prime factor if n, which is n itself if n is prime), but if n is composite, you can avoid that by doing it in random order, or by starting near √n and working down (or up). That way, even if n has only two/three prime factors, you’ll find them/one of them, but that won’t tell you that they are/one of them is prime.