My Math Forum Number of primes

 Number Theory Number Theory Math Forum

 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 timey-wimey stuff.
Quote:
 Originally Posted by matqkks How do computers evaluate the number of primes below a given integer?
I would imagine that the computer simply uses an algorithm to find the primes. I once wrote a program in High School to do this.. using a variant on the sieve of Erasthosenes.

-Dan

 September 14th, 2018, 12:42 PM #4 Member   Joined: Jul 2010 Posts: 83 Thanks: 2 If you just need a reasonable estimate N/log(N) works pretty well. More accurate approximations are covered here. Thanks from topsquark
September 15th, 2018, 07:19 AM   #5
Math Team

Joined: Oct 2011

Posts: 14,108
Thanks: 1001

Quote:
 Originally Posted by Sebastian Garth If you just need a reasonable estimate N/log(N) works pretty well.
N/log(N-1) is much closer.

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

Quote:
 Originally Posted by billymac00 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...
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:
 Originally Posted by Maschke 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?
True. But it was my interpretation they were comparing two approximations and then see which one is best.

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

Quote:
 Originally Posted by Micrm@ss True. But it was my interpretation they were comparing two approximations and then see which one is best. 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
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 Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post 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 icemanfan Number Theory 12 March 3rd, 2012 04:29 PM Agno Number Theory 53 November 19th, 2011 04:10 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top