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,489 Thanks: 950 
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,910 Thanks: 774 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,489 Thanks: 950  Quote:
https://primes.utm.edu/howmany.html  
November 4th, 2018, 04:39 AM  #6 
Senior Member Joined: Aug 2008 From: Blacksburg VA USA Posts: 342 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,082 Thanks: 595  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: 612 Thanks: 188  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,082 Thanks: 595  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,882 Thanks: 1088 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 