CODEWITHSUNDEEP
pythonalgorithm
Tenshi
Tenshi

Reputation: 13

How to print out numbers from a range generator that are not divisible by any numbers in a given list

I'm trying to print out prime numbers in a certain range and decided to go with the Segmented Sieve of Eratosthenes to find prime numbers from 2 up to sqrt(n) and use those found primes in the list to print out the prime numbers from any range such that a number in the range not divisible by any of the numbers in the sieve list ends up being a prime.

My code works for small ranges such as from 2 to 10 and 3 to 5 but starts printing out duplicates and also non-primes for large n. Any help fixing this?

from math import sqrt, ceil    

#Creating segmented sieve  

start=2    
stop=1000000000    
sieve=[i for i in range(2,ceil(sqrt(stop)+1))]    
for num in range(0,len(sieve)):    
        num2=num+1    
        while num2<len(sieve):    
            if sieve[num2]%sieve[num]==0:    
                sieve.pop(num2)    
                num2+=1    
            else:    
                num2+=1

#printing primes from start to stop using primes in sieve to ignore their multiples
    
for n in range(start,stop+1):    
    if n==sieve[0]:    
        print(n)    
        continue    
    if n%sieve[0]==0:    
        continue
    else:    
        p=1    
        while p<len(sieve):    
            if n==sieve[p]:    
                print(n)    
                p+=1    
                continue   
            if n%sieve[p]==0:
                p+=1
                continue
            else:
                p+=1
                print(n)

Upvotes: 0

Views: 107

Answers (1)

Reza Mohideen
Reza Mohideen

Reputation: 121

The problem was in the while loop. If one of the conditions in the loop is met, it means that you found a prime number so you should "break" out of the loop instead of printing it and continuing. And, to ensure that the number is checked by all numbers in the sieve list, a final conditional set so that it only breaks if the other conditions aren't met and it has reached the end of the sieve list.

     while p < len(sieve):
        if n == sieve[p]:
            print(n)
            break
        if n % sieve[p] == 0:
            break
        if p == (len(sieve)-1):
            print(n)
            break
        else:
            p += 1

Output:

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

Upvotes: 2

Related Questions