How can I prevent the numbers from repeating the number of times it is not divisible by the number it is divided?

#1

I am making a program which prints out all the numbers in the list which are prime.
First, it made a list from 1 to 10 using list comprehension and named it as num.
Then I made a list called f where the prime numbers are stored. Then I iterated over num and then wrote a piece of code which divides each number of num by a number which ranges from 2 to the number before it [range(2,x) where x is the number itself]. If the number is not divisible by any of the number in its corresponding range, it is inserted into f. Then, at last, the list f is print.

HERE IS THE CODE

The output should be:
[3,5,7] (NOTE: 2 won’t be there even though it is prime)
but I am getting the output like this
['3', '4', '5', '5', '5', '6', '6', '7', '7', '7', '7', '7', '8', '8', '8', '8', '9', '9', '9', '9', '9', '9', '1', '0', '1', '0', '1', '0', '1', '0', '1', '0', '1', '0']’
This is happening because as many times as the interpreter is seeing that the number is not divisible by a number, that many times it is inserting it into f(for example, 5 will be in f three times as it is not divisible by 2,3 and 4).
Therefore I request the community to give me suggestions so that I can rectify my code
THANK YOU

#2

So you know what is wrong in your code.

So do not insert x into f every time the x is not divisible by i. Create a boolean variable is_prime, in the for loop check if the number is prime (or if it is not a prime) and after the loop finishes - insert x into f if is_prime is True.

Your approach is highly inefficient. You are checking divisibility for every previous number. This is a lot of calculation. I suggest reading a bit about the Sieve of Eratosthenes, a much more efficient solution to your problem.

2 Likes