Python4Physics LAB
Classic v1
Home > Python > Basic Python Programs

Ch. 3.4 Finding All Prime Numbers Within a Given Range

Chapters Index
Program 1

Finding All Prime Numbers Within a Given Range

Python 3.11 Ready 

                                

                            


                            
                            

                                

                                    
Click "Run Code" to execute script and render figures.

                                

                            


                            
                                                        

                                

                                                                        

                                        
 Mathematical Problem Formulation

                                        

    
The code is executed with the defined range of 10 to 50, the steps are as follows:


    
Prime Checking:

    
The function prime(num) will be called for each number between 10 and 50.

    
For example:

    
    
        
  • prime(10) returns False (divisible by 2 and 5).
    • 
        
  • prime(11) returns True (not divisible by any number from 2 to 10).
    • 
    

    
This process continues for each number up to 50.

                                    

                                    
                                                                    

                            

                                                    

                    

                

                            
            
            
            
            
            

                

                    

                         Theoretical Principles & Computational Physics Guide
                    

                    

                        Finding All Prime Numbers Within a Given Range: Sieve of Eratosthenes & Interval Filtering                    

                    

                         Dr. Alorika Chatterjee & Dr. Anirban Shaw
                         Science & Physics Learners
                         Python 3 / NumPy / SciPy
                    

                


                
                

                    

                         1. Core Principles & Theoretical Framework
                    

                    

                        
                    

                        
 Interval Sieve: Systematically identifies all prime numbers in a bounded interval $[A, B]$ or $[2, N]$.

                        
 Algorithmic Efficiency: Instead of checking each number independently ($\mathcal{O}(N\sqrt{N})$), the Sieve of Eratosthenes eliminates composites in $\mathcal{O}(N \log \log N)$.

                        
 Scientific Density: Demonstrates the Prime Number Theorem $\pi(x) \sim x / \ln(x)$, mirroring energy level distributions in quantum chaotic systems.

                    
                    

                


                
                

                    

                         2. Mathematical Formulation & Algorithmic Pipeline
                    

                    

                        
                    
The Prime Number Theorem and asymptotic prime counting function $\pi(x)$:

                    
$$ \pi(x) \approx \frac{x}{\ln x} \approx \operatorname{Li}(x) = \int_2^x \frac{dt}{\ln t}, \quad \text{Sieve Complexity: } \mathcal{O}(N \log \log N) $$

                    

                        1. Boolean Array of Size $N+1$ →
                        2. Mark Multiples of $p \le \sqrt{N}$ as Composite →
                        3. Filter Verified Primes in $[A, B]$
                    
                    

                


                
                

                    

                         3. Numerical Mechanics & Implementation Logic
                    

                    

                        
                    
    
                        
  • Array Initialization: Create a boolean array is_prime = [True] * (limit + 1); set index 0 and 1 to False.
    • 
                        
  • Composite Marking: For each $p \ge 2$ up to $\sqrt{\text{limit}}$, if is_prime[p] is true, mark all multiples $p^2, p^2 + p, p^2 + 2p, \dots$ as False.
    • 
                        
  • Interval Extraction: Collect all indices $i \ge A$ where is_prime[i] remains True.
    • 
                        
  • Complexity Advantage: Far superior to naive trial division when generating dense prime tables for statistical mechanics.
    • 
                    
                    

                


                
                

                    

                         4. Relevant Computational Practice Exercises
                    

                    

                                                    

                                Exercise 1
                                

                                    Implement the Sieve of Eratosthenes to generate all primes up to $N = 10^5$ and compare its runtime against naive trial division.                                

                                
                            

                                                    

                                Exercise 2
                                

                                    Count twin prime pairs $(p, p + 2)$ within the range $[10, 5000]$ and compute their relative frequency.                                

                                
                            

                                                    

                                Exercise 3
                                

                                    Plot the empirical prime counting function $\pi(x)$ against the theoretical curve $x / \ln(x)$ for $x \in [10, 10^4]$.                                

                                
                            

                                            

                


                
                

                     Standard Literature & References:
                    
    
                                                    
  • Mark Newman, "Computational Physics", University of Michigan (2013).
    • 
                                                    
  • Donald E. Knuth, "The Art of Computer Programming", Addison-Wesley (1997).
    •