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 :
Post a Comment