A program that determines whether a number is prime or non-prime. (C #, Java, C ++ compatible) I made it because it often appears as a problem in programming contests such as CodeIQ.
public static bool IsPrime(int num)
{
if (num < 2) return false;
else if (num == 2) return true;
else if (num % 2 == 0) return false; //Even numbers are excluded in advance
double sqrtNum = Math.Sqrt(num);
for (int i = 3; i <= sqrtNum; i += 2)
{
if (num % i == 0)
{
//Not a prime number
return false;
}
}
//Is a prime number
return true;
}
If possible, I want to keep the code within the range that I can understand, so I am currently using this as the fastest version. (It ’s easy, right?) However, I feel that this speed is enough to solve the problem. If this is not enough, think again.
public static boolean isPrime(int num) {
if (num < 2) return false;
else if (num == 2) return true;
else if (num % 2 == 0) return false; //Even numbers are excluded in advance
double sqrtNum = Math.sqrt(num);
for (int i = 3; i <= sqrtNum; i += 2)
{
if (num % i == 0)
{
//Not a prime number
return false;
}
}
//Is a prime number
return true;
}
#include <math.h>
bool IsPrime(int num)
{
if (num < 2) return false;
else if (num == 2) return true;
else if (num % 2 == 0) return false; //Even numbers are excluded in advance
double sqrtNum = sqrt(num);
for (int i = 3; i <= sqrtNum; i += 2)
{
if (num % i == 0)
{
//Not a prime number
return false;
}
}
//Is a prime number
return true;
}
Let me give you a rough idea of the terms I didn't understand.
For the implemented algorithm, I mainly referred to the contents of this site. Primality test|Algorithm and data structure| Aizu Online Judge
On this site ** In primality test, you can use the property that "composite number x has prime factor p that satisfies p ≤ √ x". ** ** There is a description, "Composite number x has a prime factor p that satisfies p ≤ √x" = "If x is a composite number, it has a divisor less than or equal to √x" </ u> In other words, the loop end condition is up to Math.Sqrt (num). Compared to simply performing modulo operations up to num, the number of loops is reduced and the processing speed is greatly reduced.
It seems that there are roughly two types of primality test algorithms. --Decisive primality test --Probable primality test
The definitive judgment method is to make a primality test by a method that does not make any mistakes. The probabilistic judgment method is a method in which the judgment speed is dramatically increased, although errors may occur occasionally.
The representative of the deterministic primality test is "AKS Primality Test" A typical probabilistic primality test is the "Miller-Rabin primality test".
If you need a faster implementation, consider this too.
Most people will find this page useless if they know the fastest algorithm above. Please read the following only for those who want to see the implementation process leading up to the fastest algorithm.
A power technique to check if it is actually divisible while increasing the number to be divided by one. I came up with this method myself, but it was too slow.
private static bool IsPrime(int num)
{
if (num < 2) return false;
for (int i = 2; i < num; i++)
{
if (num % i == 0)
{
//Not a prime number
return false;
}
}
//Is a prime number
return true;
}
With a little ingenuity in a simple implementation, the processing speed will be halved. Simply put, we know that even numbers are divisible by 2, so let's remove them in advance. Similarly, it seems that multiples of 3 and 5 can be removed in advance, but it does not seem to be so dramatically faster.
private static bool IsPrime(int num)
{
if (num < 2) return false;
else if (num == 2) return true;
else if (num % 2 == 0) return false; //Even numbers are excluded in advance
for (int i = 3; i < num; i+=2)
{
if (num % i == 0)
{
//Not a prime number
return false;
}
}
//Is a prime number
return true;
}
Primality test-Wikipedia Primality test|Algorithm and data structure| Aizu Online Judge
Recommended Posts