PTA测试题- 素数猜想(C语言)

发布于 / C语言 / 0 条评论

原题目:

    思路其实可以更简单些,比如把判定是否是素数的函数可以写成,将待判定的数字与已判定的数字一一求余,可以省下不少运行时间。

    不过下面提供的代码是将待判定数字与从2开始的所有数字一一求余,所以运行时间也会比前者慢一些。

C代码

#include "stdio.h"

int issushu(int);

int main()
{
  int num;
  int sushu[10000];
  int count = 1;
  int ret = 0;
  scanf("%d", &num);
  sushu[0] = 2;
  for (int i = 3; i <= num; i++){
    if (issushu(i)){
      sushu[count] = i;
      count++;
    }
  }
  count--;
  for (int i = 0; i < count; i++){
    if (sushu[i + 1] - sushu[i] == 2){
      ret++;
    }
  }
  printf("%d", ret);
  {
    printf("\n");
    system("pause");
    return 0;
  }
}

int issushu(int n){
  for (int i = 2; i < n; i++){
    if(n%i == 0){
      return false;
      break;
    }
  }
  return true;
}

运行结果:

转载原创文章请注明,转载自: 斐斐のBlog » PTA测试题- 素数猜想(C语言)
目前还没有评论,快来抢沙发吧~