資料結構-第2章陣列 Array 題目 2.1一維陣列-刷題10：找出小於 n 的質數

 問題：給定一個整數 n，傳回小於 n 的質數的個數。

執行範例：輸入 10 ，輸出 4。

原因：小於10的質數有 2 3 5 7 共 4 個

import sys

def is_prime(n):

    if n == 1:

        return 0

    else:

        if n%2 == 0 and n != 2:

            return 0

        else:

            if n % 3 == 0 and n != 3:

                return 0

            else:

                for i in range(5,int(n*0.5)+1, 6):

                    if n % i == 0:

                        return 0

                    if n % (i+2) == 0:

                        return 0

    return 1

for line in sys.stdin:

    if line != '\n':

        n = int(line)

        k = 0

        for i in range(n):

            k = k + is_prime(i)

        print(k)

    else:

        break

資料來源：

1.Python 資料結構×演算法 刷題鍛鍊班：234 題帶你突破 Coding 面試的難關

 2.ZeroJudge python解答：a121. 質數又來囉

3.埃拉托斯特尼篩法
 

題目目錄

01.資料結構-第2章陣列 Array 題目 2.1一維陣列-延伸刷題：找出最大元素的位置

02.資料結構-第2章陣列 Array 題目 2.1一維陣列-範例 2.3 找出陣列中最大(或最小)的元素

03.資料結構-第2章陣列 Array 題目 2.1一維陣列-範例 2.2 刪除陣列中的指定位置的元素

04.資料結構-第2章陣列 Array 題目 2.1一維陣列-範例 2.1 插入元素到陣列中的指定位置

05.資料結構-第2章陣列 Array 題目 2.1一維陣列-刷題10：找出小於 n 的質數

06.資料結構-第2章陣列 Array 題目 2.1一維陣列-刷題11：從陣列中找出相加等於 k 的兩數

07.資料結構-第2章陣列 Array 題目 2.1一維陣列-練習題2.1 下列程式片段執行的輸出為何？

08.資料結構-第2章陣列 Array 題目 2.1一維陣列-練習題2.2 資料儲存於 A[0] ~ A[ n-1 ]。

09.資料結構-第2章陣列 Array 題目 2.1一維陣列-練習題2.3 下述程式擬找出陣列 A 中的極值

11.資料結構-第2章陣列 Array 題目 2.1一維陣列-刷題12：找零錢問題

12.資料結構-第2章陣列 Array 題目 2.1一維陣列-刷題13：比例背包問題

13.資料結構-第2章陣列 Array 題目 2.1一維陣列-刷題14：最少裝箱浪費問題

14.資料結構-第2章陣列 Array 題目 2.1一維陣列-刷題15：最大子陣列(Maximum Subarray)

15.資料結構-第2章陣列 Array 題目-2-D Array 的運算-範例 2.4 矩陣的輸出