How is prime number programmed

[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.

 

[jedishrfu]

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.

 

[rajeshmarndi]

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.

 

[micromass]

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.

 

[rasmhop]

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):

1. Set k = 2, GO TO LINE 2
2. If k * k > n, then return "n is a PRIME", else GO TO LINE 3
3. If k divides n, then return "n is a COMPOSITE", else GO TO LINE 4
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.

 

[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.

 

[micromass]

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.

 

[symbolipoint]

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.

Maybe less advanced than what others might know about, but:
Do an internet search on "Sieve of Eratosthenes".

 

[jedishrfu]

The primality tests are ordered to throw out the number as fast as possible. That means they are ordered from cheap to expensive. By expensive I mean it takes the most resources to complete which usually means takes the most time to complete.

So the cheapest is "the units digit" check and the most expensive is the "divide by all known primes less than the sqrt of the number" check.

In cryptography, they would be more interested in the factors of a number and not whether its prime especially for public key cryptography but this drives the interest for finding a complete list of primes in a certain range and in particular for finding mersenne primes for their incredible number of digits.

http://en.wikipedia.org/wiki/Mersenne_primes