題目：素數價值

?

本題可以直接用結論，或者用DP做。。。

哥德巴赫猜想：任何大于偶數都等于兩個素數和；

分類：大于2的偶數，價值為2

?????????? 奇數：若是質數價值為1，若是等于兩個質數之積價值是2，若是等于2加上某個質數價值等于2，其他價值等于3

#include <stdio.h> #include <string.h> #define N 50003bool prime[N]; int value[N]; int p[N]; int k=0;void isprime() {int i,j;memset(prime,1,sizeof(prime));memset(value,0,sizeof(value));value[2]=1;for(i=2;i<N-2;i++){if(prime[i]){p[k++]=i;value[i]=1;value[i+2]=2;for(j=i+i;j<N;j+=i){prime[j]=false;}}}int z;for(i=0;i<k;i++){for(j=0;j<k;j++){z=p[i]*p[j];if(z<N)value[z]=2;elsebreak;}}for(i=4;i<N;i+=2)value[i]=2;for(i=3;i<N;i+=2)if(value[i]==0)value[i]=3; }int main() {int a,b,t,i,s;isprime();scanf("%d",&t);while(t--){s=0;scanf("%d%d",&a,&b);for(i=a;i<=b;i++)s+=value[i];printf("%d\n",s);}return 0; }

?

總結

以上是生活随笔為你收集整理的NEFU394 素数价值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。