Fastest method to list all Prime Numbers in Python

article-featured-image

While writing code, most developers prefer to code less. And up to some point, this idea of coding less if we get the same results, is actually right. But there is another factor to look into, which is how fast your code can run and provide the desired output? And if we keep this point in mind, the idea of code less does not seem always perfect because the goal here is to provide output faster, even if it involves more code.

Below is the code to get a list of all prime numbers up to the user input limit. Below are two methods to solve this problem. Both methods provide the same results. The first method involves less code and the second method involves more code as compared to the first method. But the second method is much more efficient and faster as compared to the first method.

First method:

usr_input = int(input("Enter a number: "))
prime_numbers = []

for i in range(2, usr_input+1):
    for j in range(2, int(i**0.5)+1):
        if i % j == 0:
            break
    else:
        prime_numbers.append(i)

print(prime_numbers)

Second method:

upto = int(input("Enter the limit: "))
prime_no = []

#setting each element from 'upto' list to True
is_prime = [True] * (upto+1)

#setting each number divisble by 2 to False
for i in range(4, upto+1, 2):
    is_prime[i] = False

#setting each number divisble by 3 to False
for i in range(3, int(upto**0.5)+1, 2):
    if is_prime[i]:
        for j in range(i*i, upto+1, i):
            is_prime[j] = False

#assiging rest of the numbers to 'prime_no' list
for i in range(2, upto+1):
    if is_prime[i]:
        prime_no.append(i)

print(f"Prime numbers up to {upto} are: {prime_no}")

Both methods provide the same result. It asks user to input number and then print the list of all prime number up to user input number. But if the user input number is more than 100000 (or any bigger value), then the second method will provide result so much faster than the first method. The reason behind this is the use of loops in first method and boolean values in second method.

List all prime numbers up to certain number
protocolten-admin

Author: Harpreet Singh

Created: Thu 30 Mar 2023

Updated: 1 year, 3 months ago

Suggested Posts:
NETWORKING post image
CTF Challenges and Solutions from picoGYM by picoCTF

picoCTF is an open-source project. It's an enhanced platform for education and organizing competitions …

PROGRAMMING post image
Python Coding Challenge (Level Intermediate)

Python is one of the most powerfull programming language. Python is used in web-development, …

WINDOWS post image
Create environment variables and paths in windows

Windows environment variables and paths are essential components of the operating system, acting as pointers …

CLOUD post image
Setup AWS cross-account RDS MySQL master and slave servers

This article is about AWS RDS master and slave replication. I'll explain how to …

LINUX post image
Secure Apache against DDoS attacks using mod evasive

mod_evasive is an Apache web server module that helps protect the server against some types …

Sign up or Login to post comment.

Comments (0)