What are the method used to know bigger prime

[rajeshmarndi]

If we want to know whether a certain range of numbers, say between x and y, contain prime or not.

Do we use only the division method by all the prime less than the square root of y. If all the number are divisible, then there are no prime in that region.

Because according to the above method, if we want to know bigger prime, we need to know all the prime less than the square root of that number.Thanks.

 

[ShayanJ]

You can divide by all numbers from 2 to \sqrt{n}. This way you need no information beforehand but its a bit slower.

 

[mfb]

This can be done, but it is extremely ineffective. There are much more powerful primality tests. They can check if a 100-digit number is prime within seconds, whereas trial division (testing all smaller numbers) could not do this within the current age of the universe.

 

[rajeshmarndi]

Other forms of sieve of eratosthenes.

We can place all odd numbers in 3 column. That is 1st row is 3,5 and 7. Second row is 9,11 and 13 and so on. The 1st column can be avoided, as they are all multiples of 3. Only 2nd and 3rd column will be our focus.

We start with 5^2, it fall on the 3rd column. In fact all number square lies on the 3rd column only. All the number upto 25 are prime on the 2nd and 3rd column. We then see for next primes which when multiply with 5 fall in the 2nd column, it is 5*7=35 on the 2nd column. Now we get inital composite number of 5 on the 2nd and 3rd column. Now we just go down on both the column by 5 rows. This will strike out all composite number by 5 on both the column. Similarly with the next prime which is 7 from the above primes and go down on both the column by 7 rows.

This way it become easy to strike out all composite number of the primes, starting from their square. And the primes are visible.

Is this method easier than sieve of eratosthenes, to strike out composite number of primes?When we strike out composite number of 5 and 7 by just going down by 5 and 7 rows , we get primes upto 121. Then from there, we strike out 11 composite number, by going down by 11 rows, we get primes upto 169.

That is, when we strike out all composite number starting with their square on both 2nd and 3rd column by n primes, we get primes upto the square of the (n+1)th prime.

 

[mfb]

Is this method easier than sieve of eratosthenes, to strike out composite number of primes?

This is the sieve of Eratosthenes. It does not matter how exactly you write down the numbers, this is just a minor detail.

Anyway, this method is clearly limited by memory - in 1 TB, you cannot store data for more than a few trillion numbers. It will fail before you reach 100,000,000,000,000, and this is a tiny number compared to those used for cryptography, for example.