輸入一數字 n，印出 2 到 n 之間的質數。

print_primes.md

知道一個數字是不是質數的方法是：

如果 n 不是質數，那麼 n 一定有一個小於等於 n 的因數。

所以我們可以用下面的程式判斷輸入的 n 是否為質數：

def is_prime(n):
    for i in range(2, n):
        if n % i == 0:  # 整除，i 是 n 的因數，所以 n 不是質數。
            return False
    return True     # 都沒有人能整除，所以 n 是質數。

接著回到原題：

輸入一數字 n，印出 2 到 n 之間的質數。

這代表我們要做四件事：

1. 得到輸入值 n；
2. 跑一個迴圈產生 2 到 n 之間的數字；
3. 對迴圈的每個值，判斷它是不是質數；
4. 如果是，印出來。

前兩件事很簡單：

n = int(input('Input a number: '))  # 得到輸入值 n。

for i in range(2, n + 1):   # 產生 2 到 n 的數字。
    pass
    # TODO: 做 3. 和 4.

第三件事其實就是我們前面的那個函式。所以我們直接用它：

n = int(input('Input a number: '))  # 得到輸入值 n。

for i in range(2, n + 1):   # 產生 2 到 n 的數字。
    i_is_prime = is_prime(i)    # 判斷 i 是否為質數。

第四件事情要用一個 if 來做：

n = int(input('Input a number: '))  # 得到輸入值 n。

for i in range(2, n + 1):   # 產生 2 到 n 的數字。
    i_is_prime = is_prime(i)    # 判斷 i 是否為質數。
    if i_is_prime:              # 如果是，印出來。
        print(i)

這樣就完成了。

完整的程式：

def is_prime(n):
    for i in range(2, n):
        if n % i == 0:  # 整除，i 是 n 的因數，所以 n 不是質數。
            return False
    return True     # 都沒有人能整除，所以 n 是質數。

n = int(input('Input a number: '))  # 得到輸入值 n。

for i in range(2, n + 1):   # 產生 2 到 n 的數字。
    i_is_prime = is_prime(i)    # 判斷 i 是否為質數。
    if i_is_prime:              # 如果是，印出來。
        print(i)

print_primes_no_function.py

n = int(input('Input a number: '))

for i in range(2, n + 1):
    prime = True
    for j in range(2, i + 1):
        if i % j == 0:
            prime = False
            break
    if prime:
        print(i)

請問如果要把輸出的因數用列表表示，並且從大排到小需要怎麼打?

 def is_prime(n):
''' 判定是否為質數'''
     for i in range(2, n):
     	if (n % i == 0):  
     		return False
     return True     
 
 def dispart (num): 
''' 分解某數後將其因數由大到小排列'''
 	factor = []
 	num = int(num)
 	for n in range(2, num+1):
 		if (num%n == 0 and is_prime(n)):
 			factor.append(n)
 	return factor[::-1]
 
 if __name__ == '__main__':
	number = input ('the number: ')
 	print (dispart(number))

print_primes_no_function.py的部分應該是 ：
n = int(input('Input a number: '))

for i in range(2, n + 1):
prime = True
for j in range(2, i ):
if i % j == 0: # 可以整除的話 => 較小的數可以做為較大的數的因數的話
prime = False
break
if prime :
print(i)

如果要用while迴圈和for迴圈要怎麼寫

/*  
countPrimes(): 輸入 n 並回傳小於 n 的質數個數
*/ 
int countPrimes(int n)
{    
    if (n < 3)
        return 0;
    // 預設 prime pointer 紀錄此數值是否為 prime
    bool *Prime = malloc(n*sizeof(bool));
    memset(Prime, true, n);
    
    // 零不是質數、1 不是質數
    Prime[0] = 0, Prime[1] = 0;
    
    // 走訪所有小於等於『n 的平方根』的質數，
    // 並將質數的倍數全設為 false (not prime)
    // 不必算到 n，是因為兩因數相乘的組合至多就是 2x2 ~ sqrt(n)*sqrt(n)
    // 再往下算就重複計算了
    int sqrt_N = sqrt(n);
    for (int i = 2; i <= sqrt_N; i++)
        if (Prime[i])
            for (int j = i*i; j < n; j += i)
                    Prime[j] = false;
    
    // 線性走訪所有質數並計算個數
    int count = 0;
    for (int i = 0; i < n; i++)
        if (Prime[i])
            count++;
    return count;
}