number of primes less than n

Mar 2019
318
14
iran
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
 
Mar 2019
318
14
iran
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
 
Aug 2012
2,495
781
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:
  • Like
Reactions: 1 person
Mar 2019
318
14
iran
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
May 2013
2,522
1,049
The Astral plane
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
Dec 2006
21,479
2,470
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.
 
  • Like
Reactions: 1 person
Mar 2019
318
14
iran
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
 
  • Like
Reactions: 1 person
Mar 2019
318
14
iran
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
May 2013
2,522
1,049
The Astral plane
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