生活随笔
收集整理的這篇文章主要介紹了
跟素数相关的题
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
目錄
- 問題 A: 素數(shù)
- 問題 B: Prime Number
- 問題C: Goldbach猜想
問題 A: 素數(shù)
http://codeup.cn/problem.php?cid=100000591&pid=0
#include<cstdio>
bool a
[10005]={false};
int main(void)
{a
[2]=false;for(int i
=2;i
<=10005;i
++){if(a
[i
]==false)for(int j
=i
+i
;j
<=10005;j
=j
+i
){a
[j
]=true;}}int n
;while( scanf("%d",&n
) != EOF){bool flag
=false;for(int i
=2;i
<n
;i
++){if(!a
[i
]){if(i
%10==1){flag
=true;printf("%d ",i
);}}}if(!flag
)printf("-1");printf("\n");} return 0;
}
問題 B: Prime Number
http://codeup.cn/problem.php?cid=100000591&pid=1
題目的意思: 輸出第k個質數(shù)
#include<cstdio>
bool a
[10000005]={false};
int main(void)
{a
[2]=false;for(int i
=2;i
<=10000005;i
++){if(a
[i
]==false)for(int j
=i
+i
;j
<=10000005;j
=j
+i
){a
[j
]=true;}}int n
;while( scanf("%d",&n
) != EOF){bool flag
=false;int count
=0;for(int i
=2;i
<10000005;i
++){if(!a
[i
]){count
++;if(count
==n
){flag
=true;printf("%d",i
);break;}}}if(!flag
)printf("-1");printf("\n");} return 0;
}
問題C: Goldbach猜想
http://codeup.cn/problem.php?cid=100000591&pid=2
需要注意的是:
10=3+7
10=5+5
下面是一個比較笨的方法，只能說太憨批了。
我以為 10=5+5用雙指針的話，還得在里面再寫一個判斷條件
后來發(fā)現(xiàn)根本不用。left<=right 最后這兩指針都指向了同一個數(shù)，即 5
#include<cstdio>
bool a
[100005]={false};
int b
[10000]={0};
int main(void)
{a
[2]=false;int k
=0;for(int i
=2;i
<=100005;i
++){if(a
[i
]==false) for(int j
=i
+i
;j
<=100005;j
=j
+i
){a
[j
]=true;}}for(int i
=2;i
<=100005;i
++){if(a
[i
]==false)b
[k
++]=i
; }int n
;while(1){scanf("%d",&n
);int count
=0;if(n
==0)break;int left
,right
;left
=0;right
=k
-1;bool flag
=false;if(n
==4)printf("1\n");else{while(left
<=right
&&n
!=4){if(b
[left
]*2==n
){flag
=true;count
++;} if(b
[left
]+b
[right
]==n
){count
++;right
--;left
--;}if(b
[left
]+b
[right
]<n
){left
++;}if(b
[left
]+b
[right
]>n
){right
--;}}if(!flag
)printf("%d\n",count
);elseprintf("%d\n",count
-1);}} return 0;
}
簡單的寫法:
#include<cstdio>
bool a
[100005]={false};
int b
[10000]={0};
int main(void)
{a
[2]=false;int k
=0;for(int i
=2;i
<=100005;i
++){if(a
[i
]==false) for(int j
=i
+i
;j
<=100005;j
=j
+i
){a
[j
]=true;}}for(int i
=2;i
<=100005;i
++){if(a
[i
]==false)b
[k
++]=i
; }int n
;while(1){scanf("%d",&n
);int count
=0;if(n
==0)break;int left
,right
;left
=0;right
=k
-1;bool flag
=false;while(left
<=right
){if(b
[left
]+b
[right
]==n
){count
++;right
--;left
--;}if(b
[left
]+b
[right
]<n
){left
++;}if(b
[left
]+b
[right
]>n
){right
--;}}printf("%d\n",count
);}return 0;
}
總結
以上是生活随笔為你收集整理的跟素数相关的题的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。
