如何判斷素數

一、素數定義和判斷公式

素數（prime number）又稱質數，指在大於1的自然數中，除了1和它本身以外不再有其他因數的數，即只能被1和它本身整除的數。

對於一個數n，如果不是素數，那麼一定存在大於1且小於n的因數。因此，只需要從2開始到n-1一個一個地判斷是否能夠整除n，如果能整除，則n不是素數，否則n是素數。

判斷一個數n是否為素數，只需要用這個判斷公式：

for(i=2;i=n)
    printf("%d is a prime number.", n);
else
    printf("%d is not a prime number.", n);

在這個公式中，i用來表示控制循環，從2開始到n-1。如果n能夠被i整除，那麼n一定不是素數，跳出循環，輸出「不是素數」；否則，繼續循環。如果循環結束後i仍然小於n，那麼n不是素數；否則，n是素數。

二、如何判斷素數——C語言實現

下面是C語言實現如何判斷素數的代碼：

#include <stdio.h>
int main()
{
    int n, i;
    printf("Enter a number: ");
    scanf("%d", &n);
    for(i=2;i=n)
        printf("%d is a prime number.", n);
    else
        printf("%d is not a prime number.", n);
    return 0;
}

運行結果：

Enter a number: 23
23 is a prime number.

三、如何判斷素數——Python實現

下面是Python實現如何判斷素數的代碼：

def is_prime(n):
    for i in range(2, n):
        if n%i == 0:
            return False
    return True
 
n = int(input("Enter a number: "))
if is_prime(n):
    print(n, "is a prime number.")
else:
    print(n, "is not a prime number.")

運行結果：

Enter a number: 23
23 is a prime number.

四、如何判斷素數——C++實現

下面是C++實現如何判斷素數的代碼：

#include <iostream>
using namespace std;
int main()
{
    int n, i;
    cout<>n;
    for(i=2;i=n)
        cout<<n<<" is a prime number."<<endl;
    else
        cout<<n<<" is not a prime number."<<endl;
    return 0;
}

運行結果：

Enter a number: 23
23 is a prime number.

五、如何判斷素數——演算法程序實現

下面是一個用演算法程序實現如何判斷素數的方法:

def is_prime(n):
    if n == 1:
        return False
    elif n == 2:
        return True
    elif n%2 == 0:
        return False
    else:
        for i in range(3, int(n**0.5)+1, 2):
            if n%i == 0:
                return False
        return True
 
n = int(input("Enter a number: "))
if is_prime(n):
    print(n, "is a prime number.")
else:
    print(n, "is not a prime number.")

運行結果：

Enter a number: 23
23 is a prime number.

六、如何判斷素數——C語言實現（改進版）

下面是C語言實現如何判斷素數的改進版，採用了開方運算減小了運算量：

#include <stdio.h>
#include <math.h>
int main()
{
    int n, i, k;
    printf("Enter a number: ");
    scanf("%d", &n);
    k = sqrt(n);
    for(i=2;ik)
        printf("%d is a prime number.", n);
    else
        printf("%d is not a prime number.", n);
    return 0;
}

運行結果：

Enter a number: 23
23 is a prime number.

七、如何判斷素數——Python實現（改進版）

下面是Python實現如何判斷素數的改進版，採用了開方運算減小了運算量：

def is_prime(n):
    k = int(n**0.5)
    for i in range(2, k+1):
        if n%i == 0:
            return False
    return True
 
n = int(input("Enter a number: "))
if is_prime(n):
    print(n, "is a prime number.")
else:
    print(n, "is not a prime number.")

運行結果：

Enter a number: 23
23 is a prime number.

八、如何判斷素數——Python實現（公式版）

下面是Python實現如何判斷素數的公式版：

import math
 
def is_prime(n):
    if n <= 1:
        return False
    elif n == 2:
        return True
    elif n%2 == 0:
        return False
    else:
        for i in range(3, int(math.sqrt(n))+1, 2):
            if n%i == 0:
                return False
        return True
 
n = int(input("Enter a number: "))
if is_prime(n):
    print(n, "is a prime number.")
else:
    print(n, "is not a prime number.")

運行結果：

Enter a number: 23
23 is a prime number.