• Java
    • JAXB Tutorial
      • What is JAXB
      • JAXB Marshalling Example
      • JAXB UnMarshalling Example
  • Spring Tutorial
    • Spring Core Tutorial
    • Spring MVC Tutorial
      • Quick Start
        • Flow Diagram
        • Hello World Example
        • Form Handling Example
      • Handler Mapping
        • BeanNameUrlHandlerMapping
        • ControllerClassNameHandlerMapping
        • SimpleUrlHandlerMapping
      • Validation & Exception Handling
        • Validation+Annotations
        • Validation+ResourceBundle
        • @ExceptionHandler
        • @ControllerAdvice
        • Custom Exception Handling
      • Form Tag Library
        • Textbox Example
        • TextArea Example
        • Password Example
        • Dropdown Box Example
        • Checkboxes Example
        • Radiobuttons Example
        • HiddenValue Example
      • Misc
        • Change Config file name
    • Spring Boot Tutorial
  • Hibernate Tutorial
  • REST Tutorial
    • JAX-RS REST @PathParam Example
    • JAX-RS REST @QueryParam Example
    • JAX-RS REST @DefaultValue Example
    • JAX-RS REST @Context Example
    • JAX-RS REST @MatrixParam Example
    • JAX-RS REST @FormParam Example
    • JAX-RS REST @Produces Example
    • JAX-RS REST @Consumes Example
    • JAX-RS REST @Produces both XML and JSON Example
    • JAX-RS REST @Consumes both XML and JSON Example
  • Miscellaneous
    • JSON Parser
      • Read a JSON file
      • Write JSON object to File
      • Read / Write JSON using GSON
      • Java Object to JSON using JAXB
    • CSV Parser
      • Read / Write CSV file
      • Read/Parse/Write CSV File – OpenCSV
      • Export data into a CSV File
      • CsvToBean and BeanToCsv – OpenCSV

JavaInterviewPoint

Java Development Tutorials

Prime Number Program in Python with Optimization [Sieve of Eratosthenes & 6n+1 / 6n-1 ]

September 1, 2020 by javainterviewpoint Leave a Comment

What is a Prime Number?

A Prime Number is a number which is greater than 1 and divisible by 1 and only itself. Some of the Prime Numbers are 2, 3, 5, 7, 11, 13, 17… In this article, let’s create a Prime Number Program in Python and learn some Optimization techniques.

Prime Number Program in Python

 

Prime Number Program in Python

Is 0 a prime number?

0 is neither prime nor composite number, as per the definition, a prime number is a number with exactly two positive divisors, 1 and itself. Zero has an infinite number of divisors (we can divide 0 by all real numbers) Therefore, zero is not a Prime Number.

Is 1 a prime number?

1 is not considered as a Prime because it does not meet the criteria which is exactly two factors 1 and itself, whereas 1 has only one factor

Create a CheckPrime function

We all know that the prime numbers can only be divided by itself and 1.

If the number is less than 1, then it cannot be considered as prime. The idea behind the below code is to scan through all the integers between 2 and number-1, and if anyone of them is the divisor of the number, then the given number is not prime.

We use the modulo division to check if the number is getting divided or not. Modulo division gives us the remainder of the division. If the remainder is zero, then the number is not prime.

def checkPrime(number):
	if number < 1:
		return False
	for i in range (2, number):
		if  number % i == 0:
			return False
	return True
number = input("Enter a number to check prime ")
prime = checkPrime(int(number))
if prime:
	print(f"{number} is a prime number")
else:
	print(f"{number} is not a prime number")

Using While loop

Let’s re-write the above code using the while loop.

def checkPrime(number):
	if number < 1:
		return False
	i = 2
	while i < number:
		if  number % i == 0:
			return False
		i += 1
	return True
number = input("Enter a number to check prime ")
prime = checkPrime(int(number))
if prime:
	print(f"{number} is a prime number")
else:
	print(f"{number} is not a prime number")

The drawback of this approach is that we need to increment the i variable used in the while loop manually.

Optimization Techniques:

Technique 1: Using Square Root

While checking for Prime, we don’t have to check if the number is divisible by all the numbers till number -1. We can further optimize the above code by adding a simple range change, to check for the divisors up to the square root of the number.

Because for any number, there can be at least two factors, and one of those factors must be smaller than or equal to the square root of the number. If this is not true and both factors were larger than the square root of the number then the resulting number would be larger the number itself.

Let’s take an example 36 and analyze the factors of it, and they are 1, 2, 3, 4, 6, 9, 12, 18.

1 x 36 = 36
2 x 18 = 36
3 x 12 = 36
4 x 9 = 36
6 x 6 = 36

So, we can just iterate till 6 to find out the factors of 36

import math
def checkPrime(number):
	if number < 1:
		return False
	for i in range (2, int(math.sqrt(number))+1):
		if  number % i == 0:
			return False
	return True
number = input("Enter a number to check prime ")
prime = checkPrime(int(number))
if prime:
	print(f"{number} is a prime number")
else:
	print(f"{number} is not a prime number")

Time Complexity of the above algorithm to find factors is O(sqrt(N))

Technique 2: Sieve of Eratosthenes

Sieve of Eratosthenes works on the principle of identifying the smallest prime and eliminating all the multiples of that prime within the range.

Let’s use the Sieve of Eratosthenes approach to find prime numbers between 1 to 25. We need to iterate till the square root of 25, which is 5.

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]

Since 1 is not a prime, we can remove it.

[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]

The smallest prime is 2, and start the iteration from 2 to sqrt(number), let’s keep 2 and strikeout all the numbers which are divisible by 2

[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]

Now the next prime is 3, keep 3 and strikeout all the multiples of 3

[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]

Since 4 is stricken out, repeat the process with 5

[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]

Now, all the numbers we have are prime.

[2, 3, 5, 7, 11, 13, 17, 19, 23]

Sieve of Eratosthenes in Python

let’s implement Sieve of Eratosthenes in Python

def checkPrime(number):
	numbersList = list(range(2,number+1)) 
	for i in range(2,int(number**0.5)+1): 
		for j in range (i*i, number+1, i): 
			if j in numbersList: 
				numbersList.remove(j) 
	return numbersList
number = int(input("Enter the range to check for prime ")) 
prime = checkPrime(number) 
print(f"******* Prime numbers between 1 to {number} **********") 
print(*prime)

Technique 3: Optimized School Method [6n + 1 or 6n – 1]

The Lowest even prime is 2 and the lowest odd prime is 3. Apart from these two numbers all the prime numbers greater than 3 can be expressed in the form of 6n + 1 or 6n -1.

def checkPrime(number):
	if number <= 1:
		return False
	if number == 2 or number == 3:
		return True
	if number % 2 == 0 or number % 3 == 0:
		return False
	i = 5
	while(i * i <= number):
		if (number % i == 0 or number % (i + 2) == 0):
			return False
		i = i + 6
		return True
number = int(input("Enter a number to check for prime ")) 
prime = checkPrime(number) 
if prime: 
	print(f"{number} is a prime number") 
else: 
	print(f"{number} is not a prime number")

In the above code, we are checking the following conditions

  • When the number is less than or equal to 1 then return false as it is not a prime
  • Add exclusion for 2 and 3, if the number is 2 or 3 then return true
  • If the number is a multiple of 2 or 3 then return false
  • The loop starts with 5, which is 6n – 1  and test n % ( i + 2 ) which is 6n + 1

Python Prime Number Generator

To implement the Python prime number generator, we need to get the start and end range from the user and implement Sieve of Eratosthenes to generate all the possible prime numbers with the range.

def checkPrime(start, end): 
	numbersList = list(range(start, end+1)) 
	for i in range(2,int(end**0.5)+1): 
		for j in range (i*i, end+1, i): 
			if j in numbersList: 
				numbersList.remove(j) 
	return numbersList 
start = int(input("Enter the Starting range "))
end = int(input("Enter the Ending range "))
primeNumberList = checkPrime(start, end) 
print(f"******* Prime numbers between {start} to {end} **********") 
print(*primeNumberList)

Output:

Enter the Starting range 2
Enter the Ending range 100
******* Prime numbers between 2 to 100 **********
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Happy Learning!!

Filed Under: Python Tagged With: 6n-1, Optimization, Optimized School Method, Prime Number, Prime Number Program, Prime Number Program in Python, Sieve of Eratosthenes

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Java Basics

  • JVM Architecture
  • Object in Java
  • Class in Java
  • How to Set Classpath for Java in Windows
  • Components of JDK
  • Decompiling a class file
  • Use of Class.forName in java
  • Use Class.forName in SQL JDBC

Oops Concepts

  • Inheritance in Java
  • Types of Inheritance in Java
  • Single Inheritance in Java
  • Multiple Inheritance in Java
  • Multilevel Inheritance in Java
  • Hierarchical Inheritance in Java
  • Hybrid Inheritance in Java
  • Polymorphism in Java – Method Overloading and Overriding
  • Types of Polymorphism in java
  • Method Overriding in Java
  • Can we Overload static methods in Java
  • Can we Override static methods in Java
  • Java Constructor Overloading
  • Java Method Overloading Example
  • Encapsulation in Java with Example
  • Constructor in Java
  • Constructor in an Interface?
  • Parameterized Constructor in Java
  • Constructor Chaining with example
  • What is the use of a Private Constructors in Java
  • Interface in Java
  • What is Marker Interface
  • Abstract Class in Java

Java Keywords

  • Java this keyword
  • Java super keyword
  • Final Keyword in Java
  • static Keyword in Java
  • Static Import
  • Transient Keyword

Miscellaneous

  • newInstance() method
  • How does Hashmap works internally in Java
  • Java Ternary operator
  • How System.out.println() really work?
  • Autoboxing and Unboxing Examples
  • Serialization and Deserialization in Java with Example
  • Generate SerialVersionUID in Java
  • How to make a class Immutable in Java
  • Differences betwen HashMap and Hashtable
  • Difference between Enumeration and Iterator ?
  • Difference between fail-fast and fail-safe Iterator
  • Difference Between Interface and Abstract Class in Java
  • Difference between equals() and ==
  • Sort Objects in a ArrayList using Java Comparable Interface
  • Sort Objects in a ArrayList using Java Comparator

Follow

  • Coding Utils

Useful Links

  • Spring 4.1.x Documentation
  • Spring 3.2.x Documentation
  • Spring 2.5.x Documentation
  • Java 6 API
  • Java 7 API
  • Java 8 API
  • Java EE 5 Tutorial
  • Java EE 6 Tutorial
  • Java EE 7 Tutorial
  • Maven Repository
  • Hibernate ORM

About JavaInterviewPoint

javainterviewpoint.com is a tech blog dedicated to all Java/J2EE developers and Web Developers. We publish useful tutorials on Java, J2EE and all latest frameworks.

All examples and tutorials posted here are very well tested in our development environment.

Connect with us on Facebook | Privacy Policy | Sitemap

Copyright ©2023 · Java Interview Point - All Rights Are Reserved ·