Year 12s: what will be the first way you research your future options? >>

Is anyone good with Sieve of Eratosthenes/sieves algorithm? Need help

*PIC BELOW*

So I'm trying my hardest to understand the concept of this but I just don't get this one part.

Why aren't they diving all the listed prime numbers by 2 and 5 aswell? as those are prime. They ignored them? I don't get it

thanks again

Original post by zezno

Why aren't they diving all the listed prime numbers by 2 and 5 aswell? as those are prime. They ignored them? I don't get it

The motivation behind this algorithm is to list down numbers and then eliminate the ones that are not prime, but you can be efficient and simply not list the numbers that are obviously non-prime, such as the ones whose last digit is 0, 2, 4, 6 or 8 (i.e: divisible by 2 or 5). Once you've listed all the numbers down, you divide by primes to eliminate the ones divisible by the prime. But since you never listed down numbers divisible by 2 or 5 in the first place, there's no need to check whether 2 or 5 divide the numbers in the list.

The first paragraph clearly states that when you list the numbers the interval, you don't list, that is - you ignore and don't write down the numbers that are obviously non prime, which are the numbers divisible by 2 or 5. (they end in even digits).

So since your list has no numbers that are divisible by 2 or 5 as you've excluded them from the get-go, there's no need to check for numbers divisible by 2 or 5. I'm not sure how to make it any more clear than the explanation already given, but let me know if you don't understand and I can try clarifying.

(edited 7 years ago)

Reply 3

zezno

Original post by Zacken

The first paragraph clearly states that when you list the numbers the interval, you don't list, that is - you ignore and don't write down the numbers that are obviously non prime, which are the numbers divisible by 2 or 5. (they end in even digits).

So since your list has no numbers that are divisible by 2 or 5 as you've excluded them from the get-go, there's no need to check for numbers divisible by 2 or 5. I'm not sure how to make it any more clear than the explanation already given, but let me know if you don't understand and I can try clarifying.