Register to reply

How is prime number programmed

by rajeshmarndi
Tags: number, prime, programmed
Share this thread:
rajeshmarndi
#1
Jul2-14, 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.
Phys.Org News Partner Mathematics news on Phys.org
Heat distributions help researchers to understand curved space
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture
jedishrfu
#2
Jul2-14, 10:51 PM
P: 3,002
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
#3
Jul3-14, 09:48 AM
P: 176
Quote Quote by jedishrfu View Post
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
#4
Jul3-14, 10:19 AM
Mentor
micromass's Avatar
P: 18,334
How is prime number programmed

Quote Quote by rajeshmarndi View Post
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
#5
Jul3-14, 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 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
#6
Jul3-14, 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.
micromass
#7
Jul3-14, 11:01 AM
Mentor
micromass's Avatar
P: 18,334
Quote Quote by rajeshmarndi View Post
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
#8
Jul3-14, 01:18 PM
HW Helper
PF Gold
P: 2,823
Quote Quote by rajeshmarndi View Post
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
#9
Jul3-14, 01:29 PM
P: 3,002
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