Prime number

Question

What is the fastest way to check whether or not a number is a prime numver?

Answer 1

There are many ways to do the primality test.

Important improvement is to iterate only up through the square root of N.

static boolean primeSlightlyBetter(int n){
if (n < 2)
return false;

int sqrt = (int) Math.sqrt(n);
for (int i = 2; i <= sqrt; i++){
if (n % i == 0)
return false;
}
return true;
}

The sqrt is sufficient because, for every number X which divides N evenly, there is a
complement Y, where X*Y = N.

If X > sqrt,
then Y < sqrt (since sqrt*sqrt
= N).

We therefore don't need X to check N's primality, since we would have already checked with Y.

Of course, in reality, all we 'really' need to do is to check if N is divisible by a prime number. This is where the Sieve of Eratosthenes comes in.

Answer 2

Very hard question.
We don't know. If you can find the fastest algorithm and prove that it is the fastest you will likely become one of the most famous mathematicians of all time.

The fastest algorithm we know of so far is the AKS primality test. But it is only fast on paper and not in practice so we don't really use it in programming.

The Miller-Rabin test is a very common and fast probabilistic primality test. The sieve of Erasthotenes can also give you good mileage if you want to generate prime numbers. It depends on your application.

Answer 3

What are you trying to do?

Answer 4

https://en.m.wikipedia.org/wiki/Prime_number

Answer 5

Here is the commonly used method :
First calculate square root of a number and get the integer part of answer.Try dividing a number by 2,3,... to integer .If the number is divisible by any of the numbers between 2 and integer then number is not prime else it is prime.
Eg.√(15)=3.8729833462
Integer = 3
15 %2 != 0
15 %3 = 0
15 is not prime.
√(17) =4.1231056256
Integer= 4
17 %2 != 0
17 %3 != 0
17 %4 != 0
17 is prime.

Answer 6

I've tried the Erasthotenes one, but I still can't pass the online judging system. It timed out

Answer 7

Hm, hackerrank.com?

Answer 8

-to check whether just a number is a prime or not, use Miller-Rabin primality test or libraries which support how to check

-to list all primes below a number, use the code below (Python), I found it in Internet.

def primes(n):
n, correction = n - n % 6 + 6, 2 - ((n+1) % 6 > 1)
sieve = [True] * (n // 3)
for i in range(1, int(n ** 0.5) // 3 + 1):
if sieve[i]:
k = 3 * i + 1 | 1
sieve[k * k // 3::2 * k] = [False] * ((n // 6 - k * k // 6 - 1) // k + 1)
sieve[k * (k - 2 * (i & 1) + 4) // 3::2 * k] = [False] * (
(n // 6 - k * (k - 2 * (i & 1) + 4) // 6 - 1) // k + 1)
return [2, 3] + [3 * i + 1 | 1 for i in range(1, n // 3 - correction) if sieve[i]]

Answer 9

Nope, a local(Taiwan) one. Zerojudge

Answer 10

That method is too slow.