FilesExpand file tree

 master

/

primes_sieve_of_eratosthenes.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

40 lines (33 loc) · 1.28 KB

 master

/

primes_sieve_of_eratosthenes.py

Copy path

Top

File metadata and controls

• Code
• Blame

40 lines (33 loc) · 1.28 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

'''

Using sieve of Eratosthenes, primes(x) returns list of all primes less than x

Modification:

We don't need to check all even numbers, we can make the sieve excluding even

numbers and adding 2 to the primes list by default.

We are going to make an array of: x / 2 - 1 if number is even, else x / 2

(The -1 with even number it's to exclude the number itself)

Because we just need numbers [from 3..x if x is odd]

# We can get value represented at index i with (i*2 + 3)

For example, for x = 10, we start with an array of x / 2 - 1 = 4

[1, 1, 1, 1]

3 5 7 9

For x = 11:

[1, 1, 1, 1, 1]

3 5 7 9 11 # 11 is odd, it's included in the list

With this, we have reduced the array size to a half,

and complexity it's also a half now.

'''

def primes(x):

assert(x >= 0)

# If x is even, exclude x from list (-1):

sieve_size = (x//2 - 1) if x % 2 == 0 else (x//2)

sieve = [1 for v in range(sieve_size)] # Sieve

primes = [] # List of Primes

if x >= 2:

primes.append(2) # Add 2 by default

for i in range(0, sieve_size):

if sieve[i] == 1:

value_at_i = i*2 + 3

primes.append(value_at_i)

for j in range(i, sieve_size, value_at_i):

sieve[j] = 0

return primes