September 14th, 2018, 06: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, 07:52 AM  #2 
Math Team Joined: Oct 2011 From: Ottawa Ontario, Canada Posts: 14,108 Thanks: 1001 
How? The way it has been instructed by the programmer!

September 14th, 2018, 08:42 AM  #3  
Math Team Joined: May 2013 From: The Astral plane Posts: 2,070 Thanks: 838 Math Focus: Wibbly wobbly timeywimey stuff.  Quote:
Dan  
September 15th, 2018, 07:19 AM  #5  
Math Team Joined: Oct 2011 From: Ottawa Ontario, Canada Posts: 14,108 Thanks: 1001  Quote:
https://primes.utm.edu/howmany.html  
November 4th, 2018, 03:39 AM  #6 
Senior Member Joined: Aug 2008 From: Blacksburg VA USA Posts: 344 Thanks: 6 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, 09:41 AM  #7 
Senior Member Joined: Aug 2012 Posts: 2,191 Thanks: 643  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, 09:53 AM  #8  
Senior Member Joined: Oct 2009 Posts: 751 Thanks: 253  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, 10:52 AM  #9 
Senior Member Joined: Aug 2012 Posts: 2,191 Thanks: 643  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, 12:27 PM  #10 
Global Moderator Joined: Oct 2008 From: London, Ontario, Canada  The Forest City Posts: 7,923 Thanks: 1122 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 10:51 AM 
primes and twin primes: Number between powers of 10  caters  Number Theory  67  March 19th, 2014 04:32 PM 
problems in the primes number  WORLD  Number Theory  5  September 3rd, 2012 02:36 PM 
number of primes in a given interval  icemanfan  Number Theory  12  March 3rd, 2012 04:29 PM 
Primes as the seeds for any number  Agno  Number Theory  53  November 19th, 2011 04:10 PM 