Register to reply 
How is prime number programmed 
Share this thread: 
#1
Jul214, 09:45 PM

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. 


#2
Jul214, 10:51 PM

P: 2,809

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. 


#3
Jul314, 09:48 AM

P: 176

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. 


#4
Jul314, 10:19 AM

Mentor
P: 18,061

How is prime number programmed



#5
Jul314, 10:25 AM

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


#6
Jul314, 11:00 AM

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. 


#7
Jul314, 11:01 AM

Mentor
P: 18,061




#8
Jul314, 01:18 PM

HW Helper
PF Gold
P: 2,797

Do an internet search on "Sieve of Eratosthenes". 


#9
Jul314, 01:29 PM

P: 2,809

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 


Register to reply 
Related Discussions  
Prime Number with Prime Digits  General Math  5  
Prime numbers from infinite prime number proof  General Math  3  
Number Theory least divisor of integer is prime number if integer is not prime  Calculus & Beyond Homework  2  
A prime number which equals prime numbers  General Math  10  
A formula of prime numbers for interval (q; (q+1)^2), where q is prime number.  Linear & Abstract Algebra  0 