• 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

Python Sieve of Eratosthenes

August 18, 2020 by javainterviewpoint Leave a Comment

In this article, we will learn how to implement Python Sieve of Eratosthenes to find Prime Numbers. Sieve of Eratosthenes is an ancient algorithm used to find the prime numbers up to any given limit and it is one of the efficient ways to find prime numbers.

How Sieve of Eratosthenes works?

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

To start simple, let’s find out the prime numbers between 1 to 20

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

We will get rid of 1 because the definition of ‘prime’ excludes 1

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Now the smallest prime is 2, and any number which is divisible by 2 is not a prime number right? so, let 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

We will have the below number only, this has wiped out almost half of the list which we started with

2 3 5 7 9 11 13 15 17 19

The next prime is 3, repeat the same process and strike out all the multiples of 3

2 3 5 7 9 11 13 15 17 19 –> 2 3 5 7 11 13 17 19

Likewise, this process repeats until we get all the leftover numbers are prime numbers. In our case, we just need two iterations to get all the prime numbers between 1 to 20.

Python Sieve of Eratosthenes

Python Sieve of Eratosthenes

Lets now implement Python Sieve of Eratosthenes

import math
def printPrime(num):
	l = list(range(2,num+1))
	for i in range(2,int(math.sqrt(num)+1)):
		for j in range (i*i, num+1, i):
			if j in l:
				l.remove(j)
	return l		
num = int(input("Enter the upper limit: "))
primeList = printPrime(num)
print(f"******* Prime numbers between 1 to {num} **********")
print(*primeList)
  • We get the upper limit from the user and create a list ‘l’ using range() function.
  • Then the iteration starts from 2 [since it is the smallest prime in the given list] till the square root of the number passed.
  • Now using the inner loop we will remove the multiples of the current prime number, range (i*i, num+1, i).
    • For example, the current prime number is 2, then the inner loop will start with 4 and gets incremented by 2 for each iteration
  • For each inner loop iteration, we will check if the list ‘l’ has the particular element or not, if it has, then removes that element as it is a multiple of the current prime.
  • This loop continues and finally, we will have a list that consists of only the prime numbers.

Output:

Enter the upper limit: 44
******* Prime numbers between 1 to 44 **********
1 2 3 5 7 11 13 17 19 23 29 31 37 41 43

Filed Under: Python Tagged With: Prime, Prime Number, Python Sieve of Eratosthenes, 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 ·