September 14th, 2018, 06:52 AM  #1 
Member Joined: Apr 2011 Posts: 36 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,597 Thanks: 1038 
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,257 Thanks: 928 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,597 Thanks: 1038  Quote:
https://primes.utm.edu/howmany.html  
November 4th, 2018, 03:39 AM  #6 
Senior Member Joined: Aug 2008 From: Blacksburg VA USA Posts: 352 Thanks: 7 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,356 Thanks: 737  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: 850 Thanks: 326  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,356 Thanks: 737  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,958 Thanks: 1146 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 