here is a rule that one prome # must exist between n and 2n
so if p1 is prime then p1+1 to 2*p1 should have atleast 1 more prime
The Sieve of Eratosthenes is a recent method (dating from the 3rd century BC). The idea is this - write down all the integers up to some point:
2 3 4 5 6 7 8 9 10 11 12 13 14 15.
Now cross out all the even ones larger than 2:
2 3 4 5 6 7 8 9 10 11 12 13 14 15.
Now cross out all those divisible by 3 (other than 3):
2 3 4 5 6 7 8 9 10 11 12 13 14 15.
At each step we find the next prime (number not crossed out) publish it as a prime and cross out all of its multiples. So, in this example we see that the numbers 2, 3, 5, 7, 11, and 13 are prime.
While the sieve is an efficient way to find a large number of successive primes it cannot be used to test an arbitrary number for primality. This can be done with a pseudoprime test.
--
2 3 4 5 6 7 8 9 10 11 12 13 14 15.
Now cross out all the even ones larger than 2:
2 3 4 5 6 7 8 9 10 11 12 13 14 15.
Now cross out all those divisible by 3 (other than 3):
2 3 4 5 6 7 8 9 10 11 12 13 14 15.
At each step we find the next prime (number not crossed out) publish it as a prime and cross out all of its multiples. So, in this example we see that the numbers 2, 3, 5, 7, 11, and 13 are prime.
While the sieve is an efficient way to find a large number of successive primes it cannot be used to test an arbitrary number for primality. This can be done with a pseudoprime test.
--
♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥
No comments:
Post a Comment