Sunday, October 10, 2010

[fyzffqca] Brute forcing a result of Euler

Fermat asked, is 2^32+1 prime?

Consider all the ways the following program is "wrong" from an efficiency standpoint.  I notice half a dozen.

#include <iostream>
using namespace std; int main(){ long long x=1; x=(x<<32)+1; while(x>1) for(long long i=2;i<=x;++i) if(x%i==0){ cout<<i<<endl; x/=i; break; } }

Yet it runs fast enough:

$ time ./factorcpp 
641
6700417

real    0m0.076s
user    0m0.080s
sys    0m0.000s

Computers are so powerful that one misses out on all the math of why Fermat asked such a question, and how Euler was able to answer it with hand calculation only.

No comments :