0
p = 2
for i in range(3,10000000000000000,2):
    if p%i >= 1:
        print(i)
        p = p*(i*i)

I've tested it and it seems to work on at least the first 100 primes, will it accurately return primes indefinitely?(theoretically not literally).

user2357112
  • 260,549
  • 28
  • 431
  • 505
MoonMoon
  • 19
  • 5
  • So are you asking about python's number limitations? Or calculation errors with big numbers? – Keiwan Jun 07 '16 at 18:34
  • I'm wondering if this is a valid sieve; Will it print out a prime number every iteration. – MoonMoon Jun 07 '16 at 18:39
  • 4
    It says 27 is prime, which is incorrect: `27 == 3*3*3` – ForceBru Jun 07 '16 at 18:39
  • I assume Python 3. – Peter Wood Jun 07 '16 at 18:39
  • It also thinks 125 is a prime, but `125 == 5*5*5`, the same is for 343: `343 == 7*7*7` – ForceBru Jun 07 '16 at 18:40
  • Ah thanks i missed 27. – MoonMoon Jun 07 '16 at 18:40
  • Yeah it makes sense, If i wanted it to work I would have to multiply p by i^i not i**2. – MoonMoon Jun 07 '16 at 18:40
  • The same is for 1331, which is `11**3`. I think, now you get the point: this code thinks that a number that's equal to a prime squared is also a prime. – ForceBru Jun 07 '16 at 18:42
  • Yeah i fixed it, I changed: p = p*(i*i) to: p = p*(i ** i) – MoonMoon Jun 07 '16 at 19:00
  • Actually it wont work for all cases no matter what power i put it at, as you said its missing powers of primes, not sure if there is a way around that. – MoonMoon Jun 07 '16 at 19:06
  • If you want to ask a new question, post a new question. Your question about whether your code would work was answered. If you want to hold a conversation where people repeatedly point out how your code fails until you eventually post something that works, that's not how things work here. – user2357112 Jun 07 '16 at 19:29
  • I believe your loop `for prime in p_list` etc. could be refactored to use the `else` clause *of the `for` loop. See http://stackoverflow.com/questions/37642573/how-can-i-make-sense-of-the-else-statement-in-python-loops – Bakuriu Jun 07 '16 at 19:30
  • @user2357112 thank you for kindly pointing that out to me :) fairly new here. – MoonMoon Jun 07 '16 at 19:33

1 Answers1

1

Your limit (besides code correctness, which the comments have been pointing out) is going to be based on the maximum integer that Python allows. It turns out Python has theoretically infinite integer precision -- limited by memory.

https://docs.python.org/2/library/stdtypes.html#numeric-types-int-float-long-complex

There are four distinct numeric types: plain integers, long integers, [...]. Plain integers (also just called integers) are implemented using long in C, which gives them at least 32 bits of precision (sys.maxint is always set to the maximum plain integer value for the current platform, the minimum value is -sys.maxint - 1). Long integers have unlimited precision. [...]

So if you take sys.maxint and increase it, you still get an integer:

In [6]: sys.maxsize ** 10
Out[6]: 4455508415646675013373597242420117818453694838130159772560668808816707086990958982033203334310070688731662890013605553436739351074980172000127431349940128178077122187317837794167991459381249L

There will be, however, a performance penalty once you go beyond sys.maxsize.

rrauenza
  • 6,285
  • 4
  • 32
  • 57
  • Thanks! the sieve actually didn't work for prime powers so I had to fix it. still useful information :) – MoonMoon Jun 07 '16 at 19:23
  • Thanks @MoonMoon. When I initially read the question I thought it was about computational limits. – rrauenza Jun 07 '16 at 19:25