Python4Physics LAB
Classic v1
Home > Python > Basic Python Programs

Ch. 3.2 Determining Whether an Integer is Prime or Not

Chapters Index
Program 1

Determining Whether an Integer is Prime or Not

Python 3.11 Ready 

                                

                            


                            
                            

                                

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

                                

                            


                            
                                                        

                                

                                                                        

                                        
 Mathematical Problem Formulation

                                        
        

    
Input:

    
Given number \( n \) (e.g., \( n = 49 \)).


    
Check if \( n < 2 \):

    
If \( n \) is less than 2, return 'not prime'. (This is because prime numbers are defined as greater than 1.)


    
Initialize Loop:

    
Loop through all integers \( i \) from 2 to the integer value of the square root of \( n \) (inclusive). This is done using the range:

    

        for i in range(2, int(n**0.5) + 1)
    


    
Check for Divisibility:

    
For each \( i \) in the loop:

    
If \( n \) is divisible by \( i \) (i.e., if \( n \mod i == 0 \)): return 'not prime'. (This means that \( n \) has a divisor other than 1 and itself.)


    
Return Result:

    
If no divisors were found in the loop, return 'prime'.


    
Output:

    
Call the prime(n) function and print the result.


    
Example Walkthrough

    
For \( n = 49 \):

    
    
        
  • Check if \( 49 < 2 \): False (continue to next step).
    • 
        
  • Loop through \( i = 2 \) to \( 7 \) (the square root of \( 49 \) is \( 7 \)): 
            
      
                
    • i = 2: \( 49 \mod 2 \neq 0 \) (continue).
      • 
                
    • i = 3: \( 49 \mod 3 \neq 0 \) (continue).
      • 
                
    • i = 4: \( 49 \mod 4 \neq 0 \) (continue).
      • 
                
    • i = 5: \( 49 \mod 5 \neq 0 \) (continue).
      • 
                
    • i = 6: \( 49 \mod 6 \neq 0 \) (continue).
      • 
                
    • i = 7: \( 49 \mod 7 = 0 \) (return 'not prime').
      • 
            
    
        
    • 
    

                                    

                                    
                                                                    

                            

                                                    

                    

                

                            
            
            
            
            
            

                

                    

                         Theoretical Principles & Computational Physics Guide
                    

                    

                        Primality Testing: Divisibility Analysis & $\sqrt{N}$ Upper Bound                    

                    

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

                


                
                

                    

                         1. Core Principles & Theoretical Framework
                    

                    

                        
                    

                        
 Fundamental Building Blocks: Prime numbers are positive integers $p > 1$ divisible solely by 1 and themselves.

                        
 Square-Root Bound: If $N$ is composite, it must possess a prime factor $d \le \sqrt{N}$. Testing beyond $\sqrt{N}$ is redundant.

                        
 Physics Connection: Prime distributions connect to quantum chaos, Riemann zeta zeros, and Gaussian Unitary Ensemble energy spectra.

                    
                    

                


                
                

                    

                         2. Mathematical Formulation & Algorithmic Pipeline
                    

                    

                        
                    
Mathematical proof of divisor bounding:

                    
$$ N = a \cdot b \implies \text{if } a > \sqrt{N} \text{ and } b > \sqrt{N}, \text{ then } a \cdot b > N \text{ (contradiction)} \implies \min(a, b) \le \sqrt{N} $$
                    

                


                
                

                    

                         3. Numerical Mechanics & Implementation Logic
                    

                    

                        
                    
    
                        
  • Base Cases: If $N \le 1$, return False. If $N \in \{2, 3\}$, return True. If $N$ is even or $N \pmod 3 == 0$, return False.
    • 
                        
  • Wheel Factorization: Test potential factors $d = 6k \pm 1$ up to $\lfloor\sqrt{N}\rfloor$, stepping by 6 to skip multiples of 2 and 3.
    • 
                        
  • Computational Complexity: Reduces trial division steps from $\mathcal{O}(N)$ down to $\mathcal{O}(\sqrt{N})$.
    • 
                    
                    

                


                
                

                    

                         4. Relevant Computational Practice Exercises
                    

                    

                                                    

                                Exercise 1
                                

                                    Write an optimized primality test function implementing the $6k \pm 1$ step rule and test large primes around $10^9 + 7$.                                

                                
                            

                                                    

                                Exercise 2
                                

                                    Measure the speedup factor of testing up to $\sqrt{N}$ versus checking all integers up to $N - 1$.                                

                                
                            

                                                    

                                Exercise 3
                                

                                    Implement Fermat's primality test $a^{p-1} \equiv 1 \pmod p$ and identify a Carmichael composite pseudo-prime.                                

                                
                            

                                            

                


                
                

                     Standard Literature & References:
                    
    
                                                    
  • Donald E. Knuth, "The Art of Computer Programming, Vol. 2: Seminumerical Algorithms", Addison-Wesley (1997).
    •