I have the following two programs which search for N where (N%i == 0) for [2<=i<=20].
Java:
//Euler5 ~ Smallest multiple
import java.util.concurrent.TimeUnit;
public class Euler5
{
public static void main(String[] args) throws InterruptedException
{
long startTime = System.nanoTime();
int solution = 0;
int i = 2520;
do
{
i++;
if(((i%2)==0)&&
((i%3)==0)&&
((i%4)==0)&&
((i%5)==0)&&
((i%6)==0)&&
((i%7)==0)&&
((i%8)==0)&&
((i%9)==0)&&
((i%10)==0)&&
((i%11)==0)&&
((i%12)==0)&&
((i%13)==0)&&
((i%14)==0)&&
((i%15)==0)&&
((i%16)==0)&&
((i%17)==0)&&
((i%18)==0)&&
((i%19)==0)&&
((i%20)==0))
{
break;
}
} while(true);
long endTime = System.nanoTime();
long timeElapsed = endTime - startTime;
System.out.println("Solution: " + i + "\n");
System.out.println("Program completed in " + timeElapsed/1000000000 + " seconds.");
}
}
Which completes in <1s.
Python:
#Euler5 ~ Smallest multiple
import timeit
start = timeit.default_timer()
i = 2520;
while(1):
i = i + 1
if i%2 == 0 and \
i%3 == 0 and \
i%4 == 0 and \
i%5 == 0 and \
i%6 == 0 and \
i%7 == 0 and \
i%8 == 0 and \
i%9 == 0 and \
i%10 == 0 and \
i%11 == 0 and \
i%12 == 0 and \
i%13 == 0 and \
i%14 == 0 and \
i%15 == 0 and \
i%16 == 0 and \
i%17 == 0 and \
i%18 == 0 and \
i%19 == 0 and \
i%20 == 0:
break
stop = timeit.default_timer()
cpu_time = stop - start
if(cpu_time > 200):
print("Runtime has exceeded requirement.\n")
print("Possible solution:",i,"\n")
print("Program completed in",cpu_time,"seconds.")
exit()
#stop = timeit.default_timer()
#print("Solution: ",i,"\n")
#print("Program completed in","{0:.3f}".format(stop - start), "seconds.")
Which completes in 116.948 seconds.
Project Euler has a soft rule that programs find the solution in 60s or less. I cannot think of a way to simplify the Python program other than nesting 20 if-loops, but that seems like it would be more costly not less. And because the Java implementation is so quick it makes me wonder if there is a problem with the way I wrote the loop, such using the \ characters. I'd like to know what is going on under the hood that causes such an enormous gap in runtime.
How can I reduce the runtime of the Python program so it more closely matches the Java program?
Aucun commentaire:
Enregistrer un commentaire