Prime testA prime number is a value which only has factors of 1 and itself. Prime numbers are used fairly extensively in cryptography, as computers struggle to factorize them when they are multiplied together. The simplest test for a prime number is to divide the value from all the integers from 2 to the value divided by 2. If any of the results leaves no remainder, the value is a prime, otherwise it is composite. We can obviously improve on this by getting rid of even numbers which are greater than 2, and also that the highest value to be tested is the square root of the value. So if n = 37, then our maximum value will be √n , which, when rounded down is 6. So we can try: 2, 3, and 5, which of none of these divide exactly into 37, so it is a prime number. Now let’s try 55, we will then be 2, 3, 5 and 7. In this case 5 does divide exactly in 55, so the value is not prime. Another improvement we can make is that prime numbers (apart from 2 and 3) fit into the equation of: 6k ± 1 where k=0 gives 0 and 1, k=1 gives 5 and 7, k=2 gives 11 and 13, k=3 gives 17 and 19, and so on. Thus we can test if we can divide by 2 and then by 3, and then check all the numbers of 6k ± 1 up to √n. [Try 9][Try 11] [Try 293][Try 2,593] [Try 3,823] [Try 7,919][Try 4,487] The results are then:
|
Try an example
- Is 9 prime?. Test
- Is 11 prime?. Test
- Is 555 prime?. Test
- Is 557 prime?. Test
- Is 1059 prime?. Test
- Is 1173 prime?. Test
Sample code
public static bool get_if_prime(int val, ref string working) { working=""; int max = Convert.ToInt32(Math.Sqrt(val)); working += "Trying Divide by 2\r\n"; if (val % 2 == 0) { working += "Divisable by 2\r\n"; return (false); } working += "Trying Divide by 3\r\n"; if (val % 3 == 0) { working += "Divisable by 3\r\n"; return (false); } for (int k = 1; k < 1000; k++) { int testval = 6 * k + 1; if (testval>max) break; working += "Trying Divide by "+testval+"\r\n"; if (val % testval == 0) { working += "Divisable by "+testval; return (false); } testval = 6 * k - 1; if (testval>max) break; working += "Trying Divide by " + testval + "\r\n"; if (val % testval == 0) { working += "Divisable by " + testval; return (false); } } working += "Cannot find factor ... must be a prime" ; return (true); }
Python
The following is a Python equivalent program:
iimport math def get_if_prime(val): max = math.sqrt(val) if (val % 2 == 0): return (False) if (val % 3 == 0): return (False) for k in range(1, 10000): testval = 6 * k + 1 if (testval>max): break if (val % testval == 0): return (False) testval = 6 * k - 1; if (testval>max): break if (val % testval == 0): return (False) return (True) val=97 res = get_if_prime(val) if (res==True): print (str(val)+" is prime") else: print (str(val)+" is not prime")