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

0
votes

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?

2
pythonpython-2.7sieve-of-eratosthenes
You can check this question if it helps [stackoverflow.com/questions/3939660/… – Anurag A S
This is a side issue, but you can put number1 = int(number1) after the input and then you don't have to call int() throughout the rest of the code. – John Gordon

2 Answers

0
votes

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.

0
votes

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