怎么输出素数c语言

素数在数字领域是一种特殊的数，它只能被1和本身整除。在计算机编程领域中，素数的输出常常涉及到算法和程序设计。本文将从算法和程序设计两个角度，介绍C语言如何输出素数。

一、算法

1.1 常规算法

最常见的输出素数算法就是判断从2到该数-1是否有能够整除该数的数。若整除则说明该数不是素数，否则该数是素数。

以下是该算法在C语言中的实现：

```

#include

int main () {

int n, i, flag = 0;

printf("输入一个正整数: ");

scanf("%d", &n);

for(i=2; i<=n/2; ++i)

{

// 若能整除，则说明不是素数

if(n%i==0)

{

flag=1;

break;

}

}

if (flag==0)

printf("%d 是素数", n);

else

printf("%d 不是素数", n);

return 0;

}

```

该算法是最为基础的素数判断算法，实现简单易懂，但计算量较大，且不适用于大数的情况。

1.2 优化算法

1.2.1 方法一： 减少循环次数

在常规算法的基础上，优化算法的思路非常简单，就是找到一个有效的缩小范围的方法。由于一个数如果可以被分解成小于等于它平方根的两个数的乘积，那么这两个数中必有一个小于或等于它的平方根。所以判断是否为素数的程序可以只用判断是否能够被小于等于它的平方根的整数整除，因为如果不能，那么一定是素数。

以下是该算法在C语言中的实现：

```

#include

#include

#include

bool is_prime(int n) {

if (n <= 1) return false;

int sqrtn = (int)sqrt(n);

for (int i = 2; i <= sqrtn; i++) {

if (n % i == 0) return false;

}

return true;

}

int main () {

int n;

printf("输入一个正整数: ");

scanf("%d", &n);

if (is_prime(n))

printf("%d 是素数", n);

else

printf("%d 不是素数", n);

return 0;

}

```

1.2.2 方法二： 厄拉多塞筛法

厄拉多塞筛法是一种非常有效的筛选素数的方法。基本思路是先将2-n 中的所有数标出来，然后从2开始，将每个素数的倍数都标记成非素数，比如2的倍数、3的倍数等。经过这样的筛选，最后剩下的就是素数。

以下是该算法在C语言中的实现：

```

#include

#include

void eratosthenes(int n) {

bool prime[n+1];

for (int i = 2; i <= n; i++) prime[i] = true;

for (int i = 2; i * i <= n; i++) {

if (prime[i]) {

for (int j = i * i; j <= n; j += i) {

prime[j] = false;

}

}

}

for (int i = 2; i <= n; i++) {

if (prime[i]) printf("%d ", i);

}

}

int main() {

int n;

printf("输入一个正整数: ");

scanf("%d", &n);

eratosthenes(n);

return 0;

}

```

二、程序设计

在程序设计方面，我们需要根据这些算法，写出具体的C语言代码。

2.1 基础程序

以下是利用常规算法实现输出素数的C语言程序：

```

#include

int main () {

int n, i, flag = 0;

printf("输入一个正整数: ");

scanf("%d", &n);

for(i=2; i<=n/2; ++i)

{

// 若能整除，则说明不是素数

if(n%i==0)

{

flag=1;

break;

}

}

if (flag==0)

printf("%d 是素数", n);

else

printf("%d 不是素数", n);

return 0;

}

```

2.2 优化程序

以下是利用优化算法实现输出素数的C语言程序：

```

#include

#include

#include

bool is_prime(int n) {

if (n <= 1) return false;

int sqrtn = (int)sqrt(n);

for (int i = 2; i <= sqrtn; i++) {

if (n % i == 0) return false;

}

return true;

}

int main () {

int n;

printf("输入一个正整数: ");

scanf("%d", &n);

if (is_prime(n))

printf("%d 是素数", n);

else

printf("%d 不是素数", n);

return 0;

}

```

以下是利用厄拉多塞筛法实现输出素数的C语言程序：

```

#include

#include

void eratosthenes(int n) {

bool prime[n+1];

for (int i = 2; i <= n; i++) prime[i] = true;

for (int i = 2; i * i <= n; i++) {

if (prime[i]) {

for (int j = i * i; j <= n; j += i) {

prime[j] = false;

}

}

}

for (int i = 2; i <= n; i++) {

if (prime[i]) printf("%d ", i);

}

}

int main() {

int n;

printf("输入一个正整数: ");

scanf("%d", &n);

eratosthenes(n);

return 0;

}

```