快捷導(dǎo)航

python-leetcode求區(qū)間[M,N]內(nèi)的所有素數(shù)的個數(shù)實現(xiàn)方式

更新時間：2023年08月24日 09:32:58 作者：天下·第二

這篇文章主要介紹了python-leetcode求區(qū)間[M,N]內(nèi)的所有素數(shù)的個數(shù)實現(xiàn)方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教

python leetcode求區(qū)間[M,N]內(nèi)所有素數(shù)的個數(shù)

題目描述：

輸入M、N，1 < M < N <
1000000，求區(qū)間[M,N]內(nèi)的所有素數(shù)的個數(shù)。素數(shù)定義：除了1以外，只能被1和自己整除的自然數(shù)稱為素數(shù) 輸入描述: 兩個整數(shù)M，N
輸出描述: 區(qū)間內(nèi)素數(shù)的個數(shù)

解法一：常規(guī)解法

def prime(m, n):
    prime_list = []
    for i in range(m, n):
        for j in range(2, i):
            if i % j == 0:
                break
        else:
            prime_list.append(i)
    return len(prime_list)

解法二：使用python內(nèi)置函數(shù)filter過濾

def all_prime_number(m, n):
    filter_list = filter(lambda x: not [x % i for i in range(2, x) if x % i == 0], range(m, n))
    return len(list(prime_list))

輸出m到n之間的全部素數(shù)

本題要求輸出給定整數(shù)M和N區(qū)間內(nèi)的全部素數(shù)，每行輸出10個。素數(shù)就是只能被1和自身整除的正整數(shù)。注意：1不是素數(shù)，2是素數(shù)。

輸入格式

輸入在一行中給出兩個正整數(shù)M和N（1≤M≤N≤500）。

輸出格式

輸出素數(shù)，每個數(shù)占6位，每行輸出10個。如果最后一行輸出的素數(shù)個數(shù)不到10個，也需要換行。

若輸入的范圍不合法，則輸出"Invalid."。

輸入樣例1：

2 100

輸出樣例1：

2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97

輸入樣例2：

6 2

輸出樣例2：

Invalid.

#include<stdio.h>
#include<math.h>
int main()
{
    int i,limit,M,N,count,j;
    count=0;
    scanf("%d %d",&M,&N);
    if(M>=1&&N>=M&&N<=500)
    {
        for(i=M;i<=N;i++)
        {
            if(i==1)
                continue;
            else if(i==2){
                printf("%6d",2);
                count++;
            }else{
                limit=sqrt(i)+1;
                for(j=2;j<=limit;j++)
                {
                    if(i%j==0)
                    break;
                }
                if(j>limit){
                    printf("%6d",i);
                    count++;
                    if(count%10==0)
                    printf("\n");
                }
            }
        }
    }else{
            printf("Invalid.\n");
        }
        return 0;
}