The Sieve of Eratosthenes is a simple way, and the Sieve of Atkin a fast way, to compute the list of all prime numbers up to a given limit.
In practice, though, one usually wants to check whether a given number is prime, rather than generate a list of primes. Further, it is often satisfactory to know the answer with a high probability. It is possible to quickly check whether a given large number (say, up to a few thousand digits) is prime using probabilistic primality tests. These typically pick a random number called a "witness" and check some formula involving the witness and the potential prime N. After several iterations, they declare N to be "definitely composite" or "probably prime". Some of these tests are not perfect: there may be some composite numbers, called pseudoprimes for the respective test, that will be declared "probably prime" no matter what witness is chosen. However, the most popular probabilistic tests do not suffer from this drawback.
One method for determining whether a number is prime is to divide by all primes less than or equal to the square root of that number. If any of the divisions come out as an integer, then the original number is not a prime. Otherwise, it is a prime. One need not actually calculate the square root; once one sees that the quotients exceed the divisors, one can stop. This is known as trial division; it is the simplest primality test and it quickly becomes impractical for testing large integers because the number of possible factors grows exponentially as the number of digits in the number-to-be-tested increases.
2006-09-09 02:53:30
·
answer #1
·
answered by Anonymous
·
2⤊
0⤋
Make a square and divide it horizontally and vertically into 10 parts then there will be 100 small squares. write 100 numbers starting from 1 and ending 100. The first prime number is 2.Cross this square. Now cross all the numbers which are divisible by two i.e. 2,4,6,8,10,12,14,16...............100. Now nexxt prime number is 3. Cross it and also cross all the numbers which are divisible with 3 i.e. 6,9,12,15,18................99. contnue the procedure with next prime number i.e. 7, 11,13,17,..............
For the numbers more than 100. Take square root of that number
try to divide with all the prime numbers upto this square root of this number. Take example say 257. The square root of this is 16.03. Now divide 257 with all the prime numbers up to 16i.e 2,3,5.7,11,13 . It is not divisible by any of this therefore it is a prime number. I hope you will uderstand this method.
2006-09-09 10:22:27
·
answer #2
·
answered by Amar Soni 7
·
0⤊
0⤋
Do you mean to determine whether a particular number, say 37, is prime or not?
Divide 37 by 2 and see if the answer is a whole number; if it is, then 37 is not prime.
If not, divide 37 by 3, then by 5, then by 7, and see if the answer is a whole number.
You can stop at 7. 7^2 = 49, which is greater than 37. If you haven't found any factors by now, you won't.
2006-09-09 09:54:00
·
answer #3
·
answered by fcas80 7
·
0⤊
0⤋
No even number except for 2 can be prime, so its impossible for an even number to be prime (except for 2).and for odds, just try to find at least one thing that can go into it, and if u do, it would be composite.
2006-09-09 09:54:50
·
answer #4
·
answered by Tangerine 4
·
0⤊
0⤋
Prime numbers is only divisible by 1 and itself.
2006-09-09 09:52:51
·
answer #5
·
answered by hanna 3
·
0⤊
0⤋
If it can only be divided by itself to give the answer of one, it's a prime number
2006-09-09 09:50:07
·
answer #6
·
answered by Anonymous
·
0⤊
0⤋
Prime numbers are divisiable by itself and one.
Example:
7 ÷ 7 = 1
and
7 ÷ 1 = 7
seven cannot be factor by any other number other one and seven> therefore it is prime
2006-09-09 10:32:49
·
answer #7
·
answered by SAMUEL D 7
·
0⤊
0⤋
if u devide the number by it self and quotient is 1 so the number is prime number but remember 1 is not a prime number.
2006-09-09 09:56:10
·
answer #8
·
answered by i_m_favourite 1
·
0⤊
1⤋
You can only divide it by one and it's self and still have a whole number no decimal points.
2006-09-09 09:51:29
·
answer #9
·
answered by Crazy Diamond 6
·
0⤊
0⤋
This is just to take numbers that are disible by only one and the number itself e.g, 2,3,5.........
2006-09-09 11:15:18
·
answer #10
·
answered by nwenkiteh a 1
·
0⤊
0⤋