「prolog勉強プロジェクトオイラー131～140」の編集履歴（バックアップ）一覧に戻る
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<time>
const int Limit =1000090;
bool is_prime[Limit];
void prime_list(){
memset(is_prime,true,sizeof(is_prime));
is_prime[0]=is_prime[1]=false;
int add;
for(int i=2;i<Limit;i++){
if(is_prime[i]==false)continue;
if(i%2==0)add=i;
else add=i*2;
for(int j=i+add;j<Limit;j+=add){
is_prime[j]=false;
}
}
}
__int64 base(int p1){
__int64 Base=1;
while(Base<p1)Base*=10;
return Base;
}
__int64 mod_pow(__int64 p1,__int64 p2){
__int64 Base,Pow;
Base=Pow=base(p1);
__int64 AllPow=1,Sa=p2-p1,R=p2-2;
while(R>0){
if(R % 2==1){
AllPow=(AllPow*Pow) % p2;
}
Pow=(Pow*Pow) % p2;
R/=2;
}
return ((AllPow*Sa) % p2)*Base+p1;
}
int main(){
clock_t start,end;
start = clock();
prime_list();
__int64 ans=0,T;
int p2;
for(int p1=5;p1<1000*1000;p1+=2){
if(is_prime[p1]==false)continue;
for(p2=p1+2;is_prime[p2]==false;p2+=2){
}
ans+=mod_pow(p1,p2);
}
end= clock();
std::cout<<ans<<"\n";
std::cout<<(double)(end-start)/CLOCKS_PER_SEC<<"秒かかりました";
}
not_prime(2):-!,fail. not_prime(3):-!,fail. not_prime(N):- Limit is floor(sqrt(N)), between(2,Limit,D), (N mod D)=:=0, !. is_prime(N):-not(not_prime(N)). base(P,10):- P<10,!. base(P,100):- P<100,!. base(P,1000):- P<1000,!. base(P,10000):- P<10000,!. base(P,100000):- P<100000,!. base(P,1000000):-P<1000000,!. mod_pow(0,_,_,Result,Result):-!. mod_pow(R,P2,Pow,PowAll,Result):- R mod 2=:=1, !, R1 is R//2, Pow1 is (Pow*Pow) mod P2, PowAll1 is (PowAll*Pow) mod P2, mod_pow(R1,P2,Pow1,PowAll1,Result). mod_pow(R,P2,Pow,PowAll,Result):- !, Pow1 is (Pow*Pow) mod P2, R1 is R//2, mod_pow(R1,P2,Pow1,PowAll,Result). searchN(P2,Base,P1,Result):- Sa is P2-P1, P22 is P2-2, %X is (Base^(P2-2)*Sa) mod P2, mod_pow(P22,P2,Base,1,T), X is (T*Sa) mod P2, Result is X*Base+P1. searchP([P1,_],Ans):-1000000=<P1,!,write(Ans). searchP([P1,P2],Ans):- is_prime(P2), !, (P2 mod 1000<10->write([P2]),nl;true), base(P1,Base), searchN(P2,Base,P1,Re), Ans1 is Ans+Re, P3 is P2+1, searchP([P2,P3],Ans1). searchP([P1,P2],Ans):- P3 is P2+1, searchP([P1,P3],Ans). main134:- searchP([5,7],0).
calc1(N,T):-T is 2*N*N+1.
calc1(N,T):-T is 2*N*N-1.
gcd(0, B, G) :- G is abs(B).
gcd(A, B, G) :- A =\= 0, R is B mod A, gcd(R, A, G).
sum([],0):-!.
sum([[_,Perm]|Rest],Result):-sum(Rest,Re),Result is Re+Perm.
ok(N,[[M,N,A,B,C],Perm]):-
calc1(N,T),
T1 is floor(sqrt(T)),
T=:=T1*T1,
M is N+T1,
M>N,
1=:=(M-N) mod 2,
gcd(M,N,1),
A is M^2-N^2,
B is 2*M*N,
C is M^2+N^2,
All is A+B+C,
10^8>All,
Perm is (10^8-1)//All.
roopN(N,_):-
M is N+1,
10^8=<2*M*(M+N),
!,
fail.
roopN(N,Result):-
ok(N,Result).
roopN(N,Result):-
N1 is N+1,
roopN(N1,Result).
main139:-
findall(Ans,roopN(1,Ans),Answers),sum(Answers,Ans1),
write([ans,Ans1]).
