My Math Forum number of primes less than n

 Number Theory Number Theory Math Forum

 April 1st, 2019, 04:11 AM #1 Member   Joined: Mar 2019 From: iran Posts: 64 Thanks: 6 number of primes less than n 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
 April 1st, 2019, 04:52 AM #2 Member   Joined: Mar 2019 From: iran Posts: 64 Thanks: 6 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
 April 1st, 2019, 07:29 AM #3 Senior Member   Joined: Aug 2012 Posts: 2,265 Thanks: 690 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. Thanks from topsquark Last edited by Maschke; April 1st, 2019 at 07:54 AM.
 April 1st, 2019, 08:55 AM #4 Member   Joined: Mar 2019 From: iran Posts: 64 Thanks: 6 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 skipjack; April 1st, 2019 at 10:13 AM.
April 1st, 2019, 09:37 AM   #5
Math Team

Joined: May 2013
From: The Astral plane

Posts: 2,138
Thanks: 872

Math Focus: Wibbly wobbly timey-wimey stuff.
Quote:
 Originally Posted by 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
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 skipjack; April 1st, 2019 at 10:14 AM.

 April 1st, 2019, 10:25 AM #6 Global Moderator   Joined: Dec 2006 Posts: 20,484 Thanks: 2041 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. Thanks from topsquark
 April 1st, 2019, 10:30 AM #7 Member   Joined: Mar 2019 From: iran Posts: 64 Thanks: 6 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 Thanks from topsquark
 April 1st, 2019, 10:42 AM #8 Member   Joined: Mar 2019 From: iran Posts: 64 Thanks: 6 pi(10000) = 10000 × (1/2 × 2/3 × ... × 96/97) + pi(100) = 1203 + 25 = 1228 and true value of pi(10000) is 1229
April 1st, 2019, 10:52 AM   #9
Math Team

Joined: May 2013
From: The Astral plane

Posts: 2,138
Thanks: 872

Math Focus: Wibbly wobbly timey-wimey stuff.
Quote:
 Originally Posted by skipjack 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

 Tags number, primes

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post matqkks Number Theory 10 November 5th, 2018 02:21 PM uvkajed Number Theory 2 August 5th, 2015 10:51 AM caters Number Theory 67 March 19th, 2014 04:32 PM WORLD Number Theory 5 September 3rd, 2012 02:36 PM Agno Number Theory 53 November 19th, 2011 04:10 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top