Undergrad Number of Primes: How Computers Evaluate

Click For Summary
Computers evaluate the number of primes below a given integer using various methods, with the sieve of Eratosthenes being a prominent algorithm. Other techniques involve estimating the prime-counting function, π(x), through mathematical approximations. The accuracy of these evaluations can depend on multiple parameters, making it a complex topic. Resources are available for further exploration of algorithms and estimations related to prime numbers. Understanding these methods is crucial for computational number theory.
matqkks
Messages
282
Reaction score
5
How do computers evaluate the number of primes below a given integer?
 
Mathematics news on Phys.org
matqkks said:
How do computers evaluate the number of primes below a given integer?
This depends on so many parameters, that it can't be answered, except perhaps by the sieve of Eratosthenes, or simply by ##|\pi(x)-\operatorname{Li}(x)|<\dfrac{\sqrt{x}\ln x}{8\pi}##.

The literature has many algorithms as well as estimations for ##\pi(x)##. Just search for them.
 
  • Like
Likes Janosh89

Thread 'Area of Overlapping Squares'

Here is a little puzzle from the book 100 Geometric Games by Pierre Berloquin. The side of a small square is one meter long and the side of a larger square one and a half meters long. One vertex of the large square is at the center of the small square. The side of the large square cuts two sides of the small square into one- third parts and two-thirds parts. What is the area where the squares overlap?
View full post »

Similar threads

Graduate Is it required to use the Reimann function to solve the problem?
  • · Replies 8 ·
Replies
8
Views
1K
High School Probability that 2 distinct integers are divisible by the same number
  • · Replies 9 ·
Replies
9
Views
2K
High School Are All Imaginable Integer Series Necessarily Infinite?
  • · Replies 17 ·
Replies
17
Views
2K
Graduate Prime Number Powers of Integers and Fermat's Last Theorem
  • · Replies 1 ·
Replies
1
Views
2K
Graduate How should I write an account of prime numbers?
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Union of Prime Numbers & Non-Powers of Integers: Usage & Contexts
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad What should I say about elementary number theory?
  • · Replies 2 ·
Replies
2
Views
1K
MHB What should I say about elementary number theory?
  • · Replies 3 ·
Replies
3
Views
2K
High School Aren't There Any Formulas for Prime Numbers?
  • · Replies 7 ·
Replies
7
Views
2K
Undergrad Significance of discovering a function which computes the n-th prime?
  • · Replies 10 ·
Replies
10
Views
2K