geekdoc-python-zh/docs/overiq/092.md

C 程序：寻找素数

原文：https://overiq.com/c-examples/c-program-to-find-prime-numbers/

最后更新于 2020 年 9 月 23 日

---

什么是质数？

可被1整除或自身可整除的数称为质数。例如，11是素数，因为它只能被1和11整除。然而，数字6不是质数，因为它可以被2和3整除。以下是打印2和50之间质数的 C 程序。

/**************************************************************
 * Program to find the Prime numbers between 2 and 50
***************************************************************/

#include <stdio.h>

int main() 
{

    int is_prime = 1, n;

    for(int n = 2; n < 50; n++)
    {
        is_prime = 1;

        for(int i = 2; i < n; i++)
        {
            if(n % i == 0)
            {
                is_prime = 0;            
                break;
            }
        }

        if(is_prime)
        {
           printf("%d is prime\n", n);
        }   
    }

    return 0;
}

现在试试

预期输出:

2 is prime
3 is prime
5 is prime
7 is prime
11 is prime
13 is prime
17 is prime
19 is prime
23 is prime
29 is prime
31 is prime
37 is prime
41 is prime
43 is prime
47 is prime

工作原理:

为了检查一个质数，我们依次将一个数n从2除以n-1。如果n不能被这个范围内的任何数整除，那么它就是一个质数。

例 1:5 是素数吗？

问题	声明	结果
Is 5 可被 2 整除	5 % 2 == 0	0(假)
Is 5 可被 3 整除	5 % 3 == 0	0(假)
Is 5 可以被 4 整除	5 % 4 == 0	0(假)

因此，5是一个质数。

例 2:6 是素数吗

问题	声明	结果
Is 6 可被 2 整除	6 % 2 == 0	1(真)

数字6可被 2 整除。因此，它不是质数。

使用用户定义的函数检查素数

下面是一个使用用户定义函数检查素数的 C 程序。

/**************************************************************
 * Program to check whether the number entered by the user 
 * is prime or not
***************************************************************/

#include <stdio.h>
int check_prime_number(int);

int main() 
{
    int n;

    printf("Enter a number: ");
    scanf("%d", &n);

    if(check_prime_number(n))
    {
        printf("%d is prime", n);
    }
    else
    {
        printf("%d is not prime", n);
    }

    return 0;
}

int check_prime_number(int n)
{
    int is_prime = 1;

    if(n == 1)
    {
        return 0;
    }

    for(int i = 2; i < n; i++)
    {
        if(n % i == 0)
        {
            is_prime = 0;            
            break;
        }
    }

    return is_prime;
}

**预期输出:**第一次运行:

Enter a number: 11
11 is prime

第二次运行:

Enter a number: 45
45 is not prime

推荐阅读:

• C 程序求一个数字的位数之和
• C 程序求一个数的阶乘
• 寻找阿姆斯特朗数的 C 程序
• C 程序生成斐波那契数列
• C 程序求一个数的位数的和，直到和减少到一个位数

---

---