CODEWITHSUNDEEP
pythonpython-2.7sieve-of-eratosthenes
luciferchase
luciferchase

Reputation: 559

How to incorporate Sieve of Eratosthenes Algorithm to find prime numbers?

For clarification, this is not the same as this question Sieve of Eratosthenes - Finding Primes Python because I don't want to generate Prime Numbers between two numbers but I want to check if a number is a prime number or not.

I made the following code to find whether a number is a prime number or not. Then I heard about the Sieve of Eratosthenes Algorithm which apparently is faster, but I don't know how to write it in the following code?

number1 = int(raw_input("""
Enter any number :- """))
if number1 == 1:
    print "1 is a special case. It is neither a Prime Number nor a Normal Number. Be like 1"
if number1 == 2:
    print number1, "is a Prime Number"
if number1 == 4:
    print "4 is not a Prime Number"
    print "2 times 2 is 4"
if number1 > 1:
    for i in range(2,(number1//2)):
        if number1 % i == 0:
            print number1, "is not a Prime Number"
            print i, "times", (number1/i), "is", number1
            break
    else:
        print number1, "is a Prime Number"
else:
    print "Please type a positive number only"

Can you guys please help me?

Upvotes: 0

Views: 135

Answers (2)

Adam Smith
Adam Smith

Reputation: 54213

The Sieve of Eratosthenes is a method of generating primes. It would therefore replace your code:

for i in range(2,(number1//2)):
    if number1 % i == 0:
        # handle non-prime

with

if number1 in previous_generated_primes:
    # handle non-prime

Upvotes: 0

Jack Papel
Jack Papel

Reputation: 91

I did this on repl.it. I made it so every time I found a prime, I stored it in a list.

When calculating whether a number is prime, instead of going through all of the numbers leading up to it, I would go through all the numbers in the list.

This emulates what the sieve of eratasthenes would have you do.

Upvotes: 0

Related Questions