C语言中判断素数的方法及实现 |21xrx.com

C语言中判断素数的方法及实现

2023-06-14 21:12:05 深夜i -- --

C语言素数判断优化算法

素数是指只能被1和自身整除的正整数，判断一个数是否是素数是计算机编程中常见的问题。在C语言中，可以使用以下方法来判断一个数是否是素数：

1. 常规方法：使用循环判断

该方法循环判断2到该数的开方，如果存在一个能够整除该数的因子，则该数不是素数，否则该数是素数。具体实现如下：


#include 
#include 
int isPrime(int num) {
  int i;
  if (num <= 1) return 0;
  for (i = 2; i <= sqrt(num); i++) {
    if (num % i == 0) return 0;
  }
  return 1;
}
int main() {
  int num;
  printf("请输入一个正整数：");
  scanf("%d", &num);
  if (isPrime(num) == 1) printf("%d是素数\n", num);
  else printf("%d不是素数\n", num);
  return 0;
}

2. 优化方法：判断偶数和5的倍数

由于偶数和5的倍数在计算机中具有特殊性质，因此可以对它们进行特殊判断，避免无用的循环。具体实现如下：


#include 
#include 
int isPrime(int num) {
  int i;
  if (num <= 1) return 0;
  if (num % 2 == 0) return num == 2;
  if (num % 5 == 0) return num == 5;
  for (i = 3; i <= sqrt(num); i += 2) {
    if (num % i == 0) return 0;
  }
  return 1;
}
int main() {
  int num;
  printf("请输入一个正整数：");
  scanf("%d", &num);
  if (isPrime(num) == 1) printf("%d是素数\n", num);
  else printf("%d不是素数\n", num);
  return 0;
}

3. 进一步优化：使用埃氏筛法

埃氏筛法是一种高效的筛选小于n的素数的算法，它的基本思想是先将小于n的正整数写成一个列表，先默认所有数都是质数，然后从2开始依次遍历，每当遍历到一个数时，如果它是质数，那么就将它的倍数标记为合数，即从列表中删除，最后留下的就是小于n的素数。具体实现如下：


#include 
#include 
#include 
#include 
int* sieve(int n, int* len) {
  int i, j, count = 0;
  int* list = calloc(n, sizeof(int));
  for (i = 2; i <= n; i++) list[i - 2] = i;
  for (i = 0; i < n - 1; i++) {
    if (list[i] == 0) continue;
    count++;
    for (j = i + 1; j < n - 1; j++) {
      if (list[j] % list[i] == 0) list[j] = 0;
    }
  }
  *len = count;
  return list;
}
int isPrime(int num) {
  int i;
  if (num <= 1) return 0;
  for (i = 2; i <= sqrt(num); i++) {
    if (num % i == 0) return 0;
  }
  return 1;
}
int main() {
  int num, len, i;
  int* list;
  printf("请输入一个正整数：");
  scanf("%d", &num);
  if (num <= 1) {
    printf("%d不是素数\n", num);
    return 0;
  }
  if (isPrime(num) == 1) {
    printf("%d是素数\n", num);
    return 0;
  }
  list = sieve(num, &len);
  for (i = 0; i < len; i++) {
    if (num == list[i]) {
      printf("%d是素数\n", num);
      return 0;
    }
  }
  printf("%d不是素数\n", num);
  return 0;
}

通过埃氏筛法，在处理大量数据时可以比常规方法更加高效，同时可以在需要多次计算的情况下提高性能。

上一篇: idea打包java可执行jar包

下一篇: Java和C语言的关系探究

评论区

()

相似文章