- #26

- 70

- 0

Let's try something else.

If a number from 0 .. N is not prime it will have a factor (not necessary a prime number) lower than [tex]\sqrt{}N[/tex].

If we take the numbers from 1 to [tex]\sqrt{}N[/tex] and multiply them with numbers from 2 to [tex]\sqrt{}N[/tex] we will get [tex]\sqrt{}N[/tex] * ([tex]\sqrt{}N[/tex] - 1) = N - [tex]\sqrt{}N[/tex] numbers which have a factor lower than [tex]\sqrt{}N[/tex].

So the probability to pick a number which has a factor lower than [tex]\sqrt{}N[/tex] is somehow greater than (N - [tex]\sqrt{}N[/tex])/N, but we are looking for numbers that are prime and don't have a factor lower than [tex]\sqrt{}N[/tex]. Our probability will be therefore lower than 1 - (N - [tex]\sqrt{}N[/tex])/N = [tex]\sqrt{}N[/tex]/N which becomes 0 as N -> infinity.

Maybe you can turn this argument into a proof.

If a number from 0 .. N is not prime it will have a factor (not necessary a prime number) lower than [tex]\sqrt{}N[/tex].

If we take the numbers from 1 to [tex]\sqrt{}N[/tex] and multiply them with numbers from 2 to [tex]\sqrt{}N[/tex] we will get [tex]\sqrt{}N[/tex] * ([tex]\sqrt{}N[/tex] - 1) = N - [tex]\sqrt{}N[/tex] numbers which have a factor lower than [tex]\sqrt{}N[/tex].

So the probability to pick a number which has a factor lower than [tex]\sqrt{}N[/tex] is somehow greater than (N - [tex]\sqrt{}N[/tex])/N, but we are looking for numbers that are prime and don't have a factor lower than [tex]\sqrt{}N[/tex]. Our probability will be therefore lower than 1 - (N - [tex]\sqrt{}N[/tex])/N = [tex]\sqrt{}N[/tex]/N which becomes 0 as N -> infinity.

Maybe you can turn this argument into a proof.

Last edited: