# How is prime number programmed

by rajeshmarndi
Tags: number, prime, programmed
 P: 176 If prime number doesn't have a pattern, how it is programmed to check if a number is prime or not or to display the list of prime number under a given number. Or it just check the divisibility with each number. Thanks.
 P: 2,979 Here's a writeup on the various primality tests that are run to test a number's primeness: http://en.wikipedia.org/wiki/Primality_test Note, if the units digit of the number os 0,2,4,5,6 or 8 you know its not prime because it will be divisible by 2 or 5 or both. So only numbers with units digit of 1,3,7,9 should be tested further. When a number passes all the tests then you have run through the sequences of primes less than sqrt of the number.
P: 176
 Quote by jedishrfu So only numbers with units digit of 1,3,7,9 should be tested further. When a number passes all the tests then you have run through the sequences of primes less than sqrt of the number.
What I am asking, is that, does these primality test, check each number with units digit of 1,3,7,9 upto less than sqrt of the number.

If not, isn't the program itself is a formula for the prime number. Because the program must be following a certain pattern in it by which the program check its primality.

Or what is the difference between a program of these primality test and a formula.

Mentor
P: 18,279
How is prime number programmed

 Quote by rajeshmarndi What I am asking, is that, does these primality test, check each number with units digit of 1,3,7,9 upto less than sqrt of the number.
No.

 If not, isn't the program itself is a formula for the prime number. Because the program must be following a certain pattern in it by which the program check its primality. Or what is the difference between a program of these primality test and a formula.
Depends on how you define a formula. I guess you mean a formula to calculate the ##n##th prime. For example, you input ##n## in the formula then do some calculations and you output the ##n##th prime. The primality tests do not do that. In primality tests you input a specific number and they say whether it is prime or not. It doesn't actually give you the ##n##th prime.
 P: 424 There are several ways to check whether an integer is prime. The usual one is to simply to check for divisibility by every prime number up to the square root of your number, as you suggested. This is not the only one though. For large suspected primes you usually use algorithms which rely on random numbers and can with high certainty say whether a number is prime or not (usually the longer you run it the more certain you become). If you need complete certainty, then there are also other algorithms to check for primality which use more sophisticated methods and are faster for very large primes (see e.g. the APRT-CL algorithm). I don't understand what you are getting at with regards to what the difference is between a program and a formula. A simple and naive program might look like: PRIME(n):Set k = 2, GO TO LINE 2 If k * k > n, then return "n is a PRIME", else GO TO LINE 3 If k divides n, then return "n is a COMPOSITE", else GO TO LINE 4 Increase k by 1 and GO TO LINE 2. By my definition of a formula this wouldn't qualify as a formula, but I'm sure with a very broad view you could call it a formula.
 P: 176 But say, if there are, only few definite, if then else condition, say 4 or 5, and not an indefinite loop, the program has to go through , to find the nth prime i.e it can be done without a computer. Will it be called a formula or a program. Program I understand, where a loop can go indefinite times.
Mentor
P: 18,279
 Quote by rajeshmarndi But say, if there are, only few definite, if then else condition, say 4 or 5, and not an indefinite loop, the program has to go through , to find the nth prime i.e it can be done without a computer. Will it be called a formula or a program. Program I understand, where a loop can go indefinite times.
It all depends on your personal definition of a formula and a program.
HW Helper
PF Gold
P: 2,822
 Quote by rajeshmarndi If prime number doesn't have a pattern, how it is programmed to check if a number is prime or not or to display the list of prime number under a given number. Or it just check the divisibility with each number. Thanks.