「プロジェクトオイラー問４６」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問４６ - (2014/02/17 (月) 02:45:13) のソース

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2046

Problem 46 「もうひとつのゴールドバッハの予想」 †
Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した.

9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12

後に, この予想は誤りであることが分かった.

平方数の2倍と素数の和で表せない最小の奇合成数はいくつか?


解法
小さい数から試していきます。
i=2から初めてiを1ずつ増加させます。
iが平方数ならiとi以下の素数個々との和全部をstd::setに入れます。
iが素数ならiとi以下の平方数こことのとの和を全部std::setに入れます。
もしiを1増加させてそれが記号整数でstd::setに値がないならその数は作れない最小の数です。
Prologで効率的に書く方法は考え中。
ｃ++と違いPrologにはstd::setがないので効率的な解法はかなりめんどくさいものになりそうです。


 #include<stdio.h>
 #include<vector>
 #include<set>
 
 bool is_prime(int n){
 	if(n<2)return false;
 	for(int i=2;i*i<=n;i++){
 		if(n%i==0)return false;
 	}
 	return true;
 }
 
 bool is_square(int n){
 	int a=(int)sqrt(n);
 	return n==(a*a);
 }
 
 int main(){
 	std::vector<int> primes,squares;
 	std::set<int> memo;
 	int ans;
 	squares.push_back(1);
 	int i=2;
 	while(1){
 		if(is_square(i)){
 			squares.push_back(i);
  			for(int j=0;j<primes.size();j++){
 				memo.insert(i*2+primes[j]);
 			}
 		}
 		if(is_prime(i)){
 			primes.push_back(i);
 			for(int j=0;j<squares.size();j++){
 				memo.insert(i+squares[j]*2);
 			}
 		}
 		if((!is_prime(i))&&(i%2==1&&i>1)){
 			if(memo.find(i)==memo.end()){
 				ans=i;
 				break;
  			}
 		}
 		i++;
 	}
 	printf("%d\n",ans);
 }




 

C++コードをPrologに変更したもの。
std::setをリストのアペンドとソートを与わせてマージでしてみたが。
効率的なのか全くわからない状態。

 
 not_prime(P):-P<2,!.
 not_prime(P):-
 	between(2,P,Div),
 	(Div^2>P->!,fail;true),
 	P mod Div=:=0,
 	!.
 is_prime(P):-!,not(not_prime(P)).
 
 is_square(N):-
 	!,
 	S is floor(sqrt(N)),
 	N=:=S*S.
 
 add_list(_,[],[]):-!.
 add_list(Add,[X|Xs],[Y|Result]):-
 	!,
 	Y is X + Add,
 	add_list(Add,Xs,Result).
 
 
 cut(N,[X|Xs],[X|Xs]):-
 	N<X,
 	!.
 cut(N,[_|Xs],Result):-
 	!,
 	cut(N,Xs,Result).
 
 search(6000,_,_,_,_):-
 	!,
 	fail.
 
 
 search(N,_,_,[Top|_],N):-
 	N mod 2=:=1,
 	N<Top,
 	not_prime(N),
 	!.
  
 search(N,Primes,Squares,All,Result):-
 	!,
 	(is_prime(N)->
 	AddP is 1,Primes1=[N|Primes];
  	AddP is 0,Primes1=Primes),
 	N2 is N*2,
 	(is_square(N)->
  	AddS is 1,Squares1=[N2|Squares];
 	AddS is 0,Squares1=Squares),
 	(AddP=:=1->
 	add_list(N,Squares1,AddList1),
  	 append(All,AddList1,All1);
 	All1 = All),
 
 	(AddS=:=1->
 	add_list(N2,Primes1,AddList2),
 	append(All1,AddList2,All2);
 	All2 = All1),
 	sort(All2,All3),
 	cut(N,All3,All4),
 	N1 is N+1,
  	search(N1,Primes1,Squares1,All4,Result).
 
 main46:-
 	search(2,[],[2],[],Ans),
 	write(Ans).