Noch immer kämpfe ich darum, die Sache mit den Primfaktoren zu verstehen. Grundsätzlich läuft es gut und ich glaube am richtigen Weg zu sein.
Ich habe die Hinweise in diesem Thread dankbar angenommen, mich so gut es mir möglich war mit der Materie beschäftigt und versuche nun, das ganze auch umzusetzen.
Meine Tests verliefen bisher gut, bis ich Zahlenwerte erreicht habe, die größer als "maxint" sind.
In meiner Funktion verwende ich mehrere Male xrange(). Wenn aber einer der Werte nun größer als "maxint" ist, bekomme ich natürlich:
Code: Alles auswählen
OverflowError: long int too large to convert to intIch habe versucht die Anleitung auf Wikipedia zum Sie des Eratosthenes so gut wie mir möglich war, in Python umzusetzen.
Nur mit den großen Zahlen (Zielwert: 600851475143) gibt es nun Probleme.
Wie kann ich das umgehen?
Danke.
Code: Alles auswählen
#! /python25/python.exe
# coding: utf-8
"""Primenumbers and Primefactor.
Based on an idea to solve "Project Euler" problems."""
def getPrimes(N):
"""
getPrimes(N) -
Returns a list with prime numbers within
the given value 'N'.
Algorithm based on the one explained on
http://de.wikipedia.org/wiki/Sieb_des_Eratosthenes
'The sive of Erathosthenes'
"""
done = {}
i = 2
for i in xrange(2, N+1):
done[i] = False
i = 2
while i*i <= N+1:
if not done[i]:
j = i*i
for j in xrange(j, N+1, i):
done[j] = True
i += 1
l = []
i = 2
for i in xrange(i, N+1, 1):
if not done[i]:
l.append(i)
return l
if __name__ == "__main__":
print getPrimes(30)
print getPrimes(37)
print getPrimes(1024)
print getPrimes(600851475143)
