PAT-乙-1007 1007 素数对猜想 (20 分)

xiaoxiao2021-03-01  4

代码

#include <stdio.h> #include <string.h> #define MAX 100001 int isPrime[MAX]; int sum[MAX]; void selectPrime(){ for(int i=2; i<MAX; i++){ isPrime[i] = 1; } for(int i=2; i<MAX; i++){ if(isPrime[i]){ for(int j=i+i; j<MAX; j+=i){ isPrime[j] = 0; } } } } void count(){ memset(sum, 0, sizeof(sum)); for(int i=4; i<MAX; i++){ if(isPrime[i] && isPrime[i-2]){ sum[i] = sum[i-1] + 1; } else{ sum[i] = sum[i-1]; } } } int main(){ int num; scanf("%d", &num); selectPrime(); count(); printf("%d\n", sum[num]); return 0; }

注解

此题题意是找n以内的,差为2的素数,共有多少对。 因此关键问题是如何快速求素数。 采用筛法求素数的思想。即selectPrime()函数。先假设所有数都是素数。从2开始,2的倍数肯定都不是素数(一定有因子2)。同理,3的倍数也一定不是。一直找下去即可。 count()函数的作用是统计i和i-2都是素数,这样的素数对的数目。

此题学到的内容: (1)筛法求素数。 (2)hash打表,一次性计算出题目数据范围内的所有数,避免重复计算导致超时。 (3)memset函数赋初值0 #include <string.h> memset(sum, 0, sizeof(sum));

结果

转载请注明原文地址: https://www.6miu.com/read-3849963.html

最新回复(0)