「prolog勉強プロジェクトオイラー131~140」の編集履歴(バックアップ)一覧に戻る
not_prime(N):-N<2,!. not_prime(N):- Limit is floor(sqrt(N)), between(2,Limit,M), N mod M=:=0, !. is_prime(N):-not(not_prime(N)). test(P):- between(1,576,A), P is 3*A^2+3*A+1, is_prime(P). main131:- findall(A,test(A),Ans), write(Ans), length(Ans,Len), write(Len).
notPrime(P):- between(2,P,N), N*N =< P, P mod N=:=0, !. isPrime(P):- not(notPrime(P)). isOKNum(P):- isPrime(P), P mod 2>0, P mod 5>0. modPow(_,_,0,Sum,Sum):-!. modPow(P,Pow10,Num,Mult,Result):- Num mod 2=:=1, !, Num1 is Num//2, Pow10_1 is (Pow10*Pow10) mod P, Mult1 is (Mult*Pow10) mod P, modPow(P,Pow10_1,Num1,Mult1,Result). modPow(P,Pow10,Num,Mult,Result):- Num1 is Num//2, !, Pow10_1 is (Pow10*Pow10) mod P, modPow(P,Pow10_1,Num1,Mult,Result). f(Div,_,MinLen,MinLen):- MinLen =< Div, !. f(Div,P,MinLen,MinLen):- Div2 is Div*Div, Div2>P, !. f(Div,P,MinLen,Result):- PM is P-1, PM mod Div=:=0, !, PDiv is PM//Div, modPow(P,10,Div,1,Amari1), (Amari1=:=1 -> min(MinLen,Div,MinLen1);MinLen1 is MinLen), modPow(P,10,PDiv,1,Amari2), (Amari2=:=1 -> min(MinLen1,PDiv,MinLen2);MinLen2 is MinLen1), Div1 is Div+1, f(Div1,P,MinLen2,Result). f(Div,P,MinLen,Result):- Div1 is Div+1, !, f(Div1,P,MinLen,Result). min(A,B,A):-A<B,!. min(_,B,B):-!. search(_,20,AnsList,AnsList):-!. search(P,Count,AnsList,Result):- isOKNum(P), f(1,P,P,MinLen), (10^9) mod MinLen=:=0, !, write([P,MinLen]), Count1 is Count+1, P1 is P+1, search(P1,Count1,[P|AnsList],Result). search(P,Count,AnsList,Result):- P1 is P+1, !, search(P1,Count,AnsList,Result). sum([],0):-!. sum([X|Xs],Result):-sum(Xs,Re),Result is Re+X. main132:- search(5,0,[],AnsList), write(AnsList), sum(AnsList,Ans), write(Ans).
modPow(P,Pow10,Num,Mult,Result):- Num mod 2=:=1, !, Num1 is Num//2, Pow10_1 is (Pow10*Pow10) mod P, Mult1 is (Mult*Pow10) mod P, modPow(P,Pow10_1,Num1,Mult1,Result). modPow(P,Pow10,Num,Mult,Result):- Num1 is Num//2, !, Pow10_1 is (Pow10*Pow10) mod P, modPow(P,Pow10_1,Num1,Mult,Result). f(Div,P,MinLen,MinLen):- Div2 is Div*Div, Div2>P, !. f(Div,P,MinLen,Result):- PM is P-1, PM mod Div=:=0, !, PDiv is PM//Div, modPow(P,10,Div,1,Amari1), (Amari1=:=1 -> min(MinLen,Div,MinLen1);MinLen1 is MinLen), modPow(P,10,PDiv,1,Amari2), (Amari2=:=1 -> min(MinLen1,PDiv,MinLen2);MinLen2 is MinLen1), Div1 is Div+1, f(Div1,P,MinLen2,Result). f(Div,P,MinLen,Result):- Div1 is Div+1, !, f(Div1,P,MinLen,Result). min(A,B,A):-A<B,!. min(_,B,B):-!. div2or5(P,P1):-P mod 5=:=0,!,P1 is P//5. div2or5(P,P1):-P mod 2=:=0,!,P1 is P//2. is2or5(1):-!. is2or5(P):-div2or5(P,P1), is2or5(P1). searchMin(P):- f(1,P,P,MinLen), !, not(is2or5(MinLen)). all_search(P):- between(11,100000,P), isPrime(P), searchMin(P). sum([],0):-!. sum([X|Xs],Result):-sum(Xs,Re),Result is Re+X. main133_2:- findall(P,all_search(P),Ps), sum(Ps,Ans), Ans1 is Ans+2+3+5+7, write([Ans1]).
#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]).