1

My code:

import math
n=int(input('Enter the number'))
b=list(range(2,n+1))
for i in range(2,int(math.sqrt(n))+1):
    for j in b:
        if j!=i and j%i==0:
            b[b.index(j)]=0

b={i for i in b if not i==0}
c={i for i in b if n%i==False}
print(b)
print(c)

This one, I implemented the sieve in my way. Why does it not work for Project Euler question 3 for the number 600851475143? I am getting:

Enter the number600851475143
Traceback (most recent call last):
  File "C:/Users/raja/AppData/Local/Programs/Python/Python37-32/ui.py", line 6, in <module>
    b=list(range(2,n+1))
OverflowError: Python int too large to convert to C ssize_t

I am just a beginner and self-taught.I'm welcoming all suggestions that are simple and please do point out my mistakes in a kind way:). Thank You.

khelwood
  • 55,782
  • 14
  • 81
  • 108
Jayasri Palanisamy
  • 39
  • 4
  • 3
    If I'm counting correctly, you are trying to make a 600 billion entry list, which might require over 2 TB of memory... Perhaps the Sieve of Eratosthenes is not the right algorithm? – Ken Y-N Aug 28 '20 at 07:11
  • 2
    `n%i==False` is a confusing way to write `n%i==0` – khelwood Aug 28 '20 at 07:11
  • What is the right algorithm then???@ Ken Y-N – Jayasri Palanisamy Aug 28 '20 at 07:15
  • 1
    Does this answer your question? [Algorithm to find Largest prime factor of a number](https://stackoverflow.com/questions/23287/algorithm-to-find-largest-prime-factor-of-a-number) – Ken Y-N Aug 28 '20 at 07:19

1 Answers1

0

Sieve of eratosthenes is used to find all prime numbers in a given range with constant lookup time with o(n) space and time complexity. So it's better to use when you need to check many numbers for prime condition. Since space complexity is o(n) hence for High numbers it requires huge space.

If you need to check for prime once then you are better off with calculating it on the fly with o(n) time complexity and o(1) space complexity.

Saurabh Nigam
  • 795
  • 6
  • 12