# number of primes less than n

#### youngmath

is this correct?
pi(n) = number of primes less than n
pi(n) = n Ã— (1/2 Ã— 2/3 Ã— 4/5 Ã— ... Ã— p-1/p)
p = largest prime less than square root of n

#### youngmath

proof
a prime number is a number that isn't divisible by primes less than or equal to it's square root
1/2 of numbers are not divisible by 2
2/3 of them are not divisible by 3
4/5 of them are not divisible by 5
.
.
.
p-1/p of them are not divisible by p
p = largest prime equal to or less than square root of given number
so number of primes less than n is n Ã— product of these fractions

#### Maschke

Half of the numbers aren't divisible by 2. Then 2/3 of the numbers aren't divisible by 3 ... but you counted 6 twice so you have to account for that. Likewise 4/5 aren't divisible by 5 but you counted 10 and 15 twice, etc. So your formula works once you put in all the correction factors, which make it a lot more complicated.

Last edited:
1 person

#### youngmath

I didn't count composite numbers like 6 or 10. I counted prime numbers;
half of numbers are not divisible by 2 (odd numbers)
1 3 5 7 9 11
as you see, 2/3 of them (odd numbers) are not divisible by 3 (1 5 7 11)
1/2 Ã— 2/3 = 1/3 of numbers are not divisible by 2 or 3

Last edited by a moderator:

#### topsquark

Math Team
I didn't count composite numbers like 6 or 10. I counted prime numbers;
half of numbers are not divisible by 2 (odd numbers)
1 3 5 7 9 11
as you see, 2/3 of them (odd numbers) are not divisible by 3 (1 5 7 11)
1/2 Ã— 2/3 = 1/3 of numbers are not divisible by 2 or 3
You aren't making your list long enough.
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49 for example.

I count 15 primes out of 25 numbers. The ratio is closer to 1/2 than 1/3. This shows that your ratio of 2/3 is only an approximation. Part of the trouble here is that you have to have the whole list of primes to do your ratios. Unfortunately, that list is infinite, so you are stuck with approximations.

-Dan

Last edited by a moderator:

#### skipjack

Forum Staff
Of those 25 numbers, 14 are prime and 10 are composite.

The 10 composite numbers comprise 7 that divide by 3, 2 that divide by 5 (but not by 3) and 1 that divides by 7 (but not by 3 or 5).

Hence youngmath's method works quite well for the above example.

1 person

#### youngmath

this formula does't count prime numbers less than square root of n
true formula is:
pi(n) - pi(âˆšn) = n Ã— (1/2 Ã— 2/3 Ã— 4/5 Ã— ... Ã— p-1/p)
p = largest prime less than or equal to square root of n

1 person

#### youngmath

pi(10000) = 10000 Ã— (1/2 Ã— 2/3 Ã— ... Ã— 96/97) + pi(100) = 1203 + 25 = 1228 and true value of pi(10000) is 1229

#### topsquark

Math Team
Of those 25 numbers, 14 are prime and 10 are composite.

The 10 composite numbers comprise 7 that divide by 3, 2 that divide by 5 (but not by 3) and 1 that divides by 7 (but not by 3 or 5).

Hence youngmath's method works quite well for the above example.
I see, thanks for the catch. I was doing it wrong.

-Dan