Google Miller-Rabin test (tho it's not O(log(n))). Also, there is a blog made by peltorator on a simpler method, but unfortunately it is written in russian. https://telegra.ph/Prostoj-test-na-prostotu-09-25

i think the best way is in $$$O(\sqrt n)$$$ which is easy and pretty fast (although not as fast as $$$O(log(n))$$$)

You can precompute it for every integer between $$$1$$$ and $$$A$$$ using Sieve of Eratosthenes. I always use normal one that works in $$$O(AlogA)$$$, but there exists a linear one that works in $$$O(A)$$$

If you only want to see for one number $$$n$$$ if it is prime you can do it in $$$O(\sqrt n)$$$

There is a probabilistic algorithm. The Fermat's last theorem states that if $$$p$$$ is a prime and $$$a$$$ is a natural number that is not divisible by $$$p$$$, then $$$p$$$ divides $$$a^p - a$$$. It doesn't hold in the opposite direction all the time but most of the time. So if you have some natural number $$$p$$$, just check the condition $$$p$$$ divides $$$a^p - a$$$ for many different a and if all of them hold you are very likely to have a prime number. Time complexity is $$$O(k \log n)$$$ with fast exponentiation where $$$k$$$ is the number of different $$$a$$$ you try. If implemented carefully and correctly you can have an algorithm that is correct practically 100% of the time.

The fastest primality test currently is AKS, in 6th power of the logarithm. Essentially making it polynomial in bit size, hence making PRIMES a part of P.

Method 1:O(logN) The above judgment method clearly has the problem of extremely low efficiency. For each number n, it is not necessary to judge from 2 to n-1. We know that if a number can be factorized, the two numbers obtained during factorization must be one less than or equal to sqrt (n) and one greater than or equal to sqrt (n). Based on this, the above code does not need to traverse to n-1, it only needs to traverse to sqrt (n), because if the divisor cannot be found on the left side of sqrt (n), then the divisor 12 cannot be found on the right side either.

1×12=12 2×6=12 3×4=12 4×3=12

Numbers that can be divided by 2 are definitely not prime numbers, so they do not need to be divided by 4 or 6, which can reduce the number of n/2 executions. Numbers that can be divided by 3 are definitely not prime numbers, so they do not need to be divided by 6 or 9, which can further reduce the number of executions.

int isPrime(num) {
	if(num ==2|| num==3 )
		return num;
	//Perform open computation here
	for (var i = 2; i <= temp; i++) {
		if(num % i ==0) {
			return false;
		}
	}
	return num;
}

Method 2:O(logN/2) 2x, 3x, 5x are definitely not prime numbers.

At this point, it is possible to fast forward 2 prime numbers as a unit, that is, in the loop, the i++step size is increased to 2, which speeds up the judgment process.

int isPrime(num) {
	if(num ==2 || num==3)
		return num;
	if(num % 2 == 0 || num % 3 == 0 || num % 5 == 0)
		return false;
	//Perform open computation here
	for (int i = 7; i <= temp; i=i+2) {
		if(num % i == 0) {
			return false;
		}
	}
	return num;
}

Method 3:O(logN/6) Proof: Let x ≥ 1, and express the natural numbers greater than or equal to 5 as follows:

······ 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ······

As can be seen, the numbers outside the sides of multiples of 6 are 6x+2, 6x+3, and 6x+4. Since 2 (3x+1), 3 (2x+1), and 2 (3x+2) are not prime numbers, and 6x itself is not prime. So on both sides of multiples of 6 must be prime numbers, and: if (num% 6!=1&&num% 6!=5) return false; Adjacent sides of multiples of 6 are not necessarily prime numbers. At this point, it is possible to fast forward 6 prime numbers as units, which means that in the loop, the i++step size is increased to 6, speeding up the judgment process. The reason is that if the number to be determined is n, then n must be in the form of 6x-1 or 6x+1. For loops 6i-1, 6i, 6i+1, 6i+2, 6i+3, and 6i+4, if n can be divided by 6i, 6i+2, and 6i+4, then n must be at least an even number. However, the form of 6x-1 or 6x+1 is clearly an odd number, so it does not hold. In addition, if n can be divided by 6i+3, then n can be divided by 3 at least, but 6x can be divided by 3, so 6x-1 or 6x+1 (i.e. n) cannot be divided by 3, so it does not hold. In summary, only the cases of 6i-1 and 6i+1 need to be considered in the loop, that is, the step size of the loop can be set to 6, and each time the loop variables k and k+2 are judged, the overall speed should theoretically be three times that of method (2).

int isPrime(num) {
	if(num == 2 || num == 3 )
		return num ;
	if(num%6 != 1 && num%6 != 5) {
		return false ;
	}
	int tmp = sqrt(num);
	for(int i = 5; i <= tmp; i+=6 )
		if(num % i == 0 || num%(i + 2) == 0)
			return false;
	return num;
}

I hope my advice can help you. If there are some mistakes, please point them out and I am very happy to correct them. Thanks for your reading.

You can check out this blog that i found interesting blog