My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree4Thanks
Reply
 
LinkBack Thread Tools Display Modes
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?
matqkks is offline  
 
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!
Denis is online now  
September 14th, 2018, 09:42 AM   #3
Math Team
 
topsquark's Avatar
 
Joined: May 2013
From: The Astral plane

Posts: 1,910
Thanks: 774

Math Focus: Wibbly wobbly timey-wimey stuff.
Quote:
Originally Posted by matqkks View Post
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
topsquark is offline  
September 14th, 2018, 01: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
Sebastian Garth is offline  
September 15th, 2018, 08:19 AM   #5
Math Team
 
Joined: Oct 2011
From: Ottawa Ontario, Canada

Posts: 13,489
Thanks: 950

Quote:
Originally Posted by Sebastian Garth View Post
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
Thanks from Sebastian Garth and topsquark
Denis is online now  
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...
billymac00 is offline  
November 4th, 2018, 10:41 AM   #7
Senior Member
 
Joined: Aug 2012

Posts: 2,082
Thanks: 595

Quote:
Originally Posted by billymac00 View Post
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?
Maschke is offline  
November 4th, 2018, 10:53 AM   #8
Senior Member
 
Joined: Oct 2009

Posts: 612
Thanks: 188

Quote:
Originally Posted by Maschke View Post
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
Micrm@ss is offline  
November 4th, 2018, 11:52 AM   #9
Senior Member
 
Joined: Aug 2012

Posts: 2,082
Thanks: 595

Quote:
Originally Posted by Micrm@ss View Post
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.
Maschke is offline  
November 4th, 2018, 01:27 PM   #10
Global Moderator
 
greg1313's Avatar
 
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.
greg1313 is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2018 My Math Forum. All rights reserved.