September 14th, 2018, 07:52 AM  #1 
Member Joined: Apr 2011 Posts: 31 Thanks: 0  Number of primes
How do computers evaluate the number of primes below a given integer?

September 14th, 2018, 08:52 AM  #2 
Math Team Joined: Oct 2011 From: Ottawa Ontario, Canada Posts: 13,804 Thanks: 971 
How? The way it has been instructed by the programmer!

September 14th, 2018, 09:42 AM  #3  
Math Team Joined: May 2013 From: The Astral plane Posts: 1,981 Thanks: 790 Math Focus: Wibbly wobbly timeywimey stuff.  Quote:
Dan  
September 15th, 2018, 08:19 AM  #5  
Math Team Joined: Oct 2011 From: Ottawa Ontario, Canada Posts: 13,804 Thanks: 971  Quote:
https://primes.utm.edu/howmany.html  
November 4th, 2018, 04:39 AM  #6 
Senior Member Joined: Aug 2008 From: Blacksburg VA USA Posts: 343 Thanks: 5 Math Focus: primes of course  another estimate
Based on work by Kristyan (see Talk page of the link given by Garth) , his estimate of ( N/lnN + N/lnN^2) seems even better...

November 4th, 2018, 10:41 AM  #7 
Senior Member Joined: Aug 2012 Posts: 2,136 Thanks: 623  How could an inexact approximation be better than the exact number? Of course asymptotics are important and valuable, but for accuracy you can't beat exactness. Right?

November 4th, 2018, 10:53 AM  #8  
Senior Member Joined: Oct 2009 Posts: 706 Thanks: 238  Quote:
Or are you asking why we care at all about approximative forms like N/log(N), when we have the exact form? That's a good question  
November 4th, 2018, 11:52 AM  #9 
Senior Member Joined: Aug 2012 Posts: 2,136 Thanks: 623  I hadn't read the rest of the thread. I thought they were comparing asymptotics to exact (but slow) algorithms. But if they're just comparing different asymptotic approximations, that makes more sense.

November 4th, 2018, 01:27 PM  #10 
Global Moderator Joined: Oct 2008 From: London, Ontario, Canada  The Forest City Posts: 7,900 Thanks: 1094 Math Focus: Elementary mathematics and beyond 
It's worth mentioning that approximations can practically handle much larger numbers and become more accurate as N increases in size.


Tags 
number, primes 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Conjecture about the number of primes  uvkajed  Number Theory  2  August 5th, 2015 11:51 AM 
primes and twin primes: Number between powers of 10  caters  Number Theory  67  March 19th, 2014 05:32 PM 
problems in the primes number  WORLD  Number Theory  5  September 3rd, 2012 03:36 PM 
number of primes in a given interval  icemanfan  Number Theory  12  March 3rd, 2012 05:29 PM 
Primes as the seeds for any number  Agno  Number Theory  53  November 19th, 2011 05:10 PM 