首页 > 试题广场 >

连续质数表示

[编程题]连续质数表示

热度指数：484 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一些正数能被表示成一个或者多个连续质数的和。那一个数会有多少种这样的表示方式呢？比如说数字41能有3种表示方式：2+3+5+7+11+13，11+13+17，和41；数字3只有本身这一种表示方式；而20没有这样的表示方式。写一个程序生成给定数字的表示方式数量吧。数字大小范围从2到10，000。

输入描述:

一行，包含一个2到10000的正整数

输出描述:

一行, 非负整数, 给定数字的表示方式数量

示例1

输入

输出

算法知识视频讲解

pein531

先求取不超过n的素数表，然后穷举素数表的连续子数组和，找出满足和为n的即可

def isPrime(num):
    for factor in range(2, num):
        if num % factor == 0:
            return False
    return True

if __name__ == "__main__":
    n = int(input())
    prime_list = []
    # 先生成不超过n的质数表
    for i in range(2, n + 1):
        if isPrime(i):
            prime_list.append(i)
    count, start, prime_num = 0, 0, len(prime_list)
    while start <= prime_num - 1:
        for L in range(1, prime_num - start + 1):
            temp = sum(prime_list[start:start + L])
            if temp > n:
                break
            if temp == n:
                count += 1
        start += 1
    print(count)

发表于 2021-04-11 20:41:17 回复(0)

xuyjbug404

滑动窗口// 队列，求连续质数和

import queue
def is_prime(n:int):
    for i in range(2, n-1):
        if n % i == 0:
            return 0
    return 1

n = int(input())
count = is_prime(n)
primes = queue.Queue()

sum_ = 0
for i in range(n-1,1,-1):
    if is_prime(i) == 1:
        primes.put(i)
        if sum_ + i < n:
            sum_ += i
        else:
            if sum_ + i == n:
                count += 1
            sum_ = sum_ + i - primes.get()

print(count)

编辑于 2022-07-23 17:22:27 回复(1)

C++

Zaneking

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int prime[n+1];
    memset(prime,0,sizeof(prime));
    vector<int> m;
    for(int i=2;i<=n;i++)
    {
        if(prime[i]==0)
        {
            m.push_back(i);
        }
        for(int j=i+i;j<=n;j=j+i)
        {
            prime[j]=1;
        }
        //cout<<"hello"<<endl;
    }
    //cout<<"***"<<endl;
    //cout<<m.size()<<endl;
    int result=0;
    int cnt=0;
    int from=0;
    int to=0;
    while(to<m.size() && from<=to)
    {
        //cout<<m[to]<<endl;
        if(m[to]+result<n)
        {
            result=result+m[to];
            to++;
            continue;
        }
        else if(m[to]+result==n)
        {
            result=result+m[to]-m[from];
            from++;
            to++;
            cnt++;
            continue;
        }
        else
        {
            result=result-m[from];
            from++;
            continue;
        }
    }
    cout<<cnt<<endl;
    
}

发表于 2022-01-03 12:40:02 回复(0)

Python

maoxiaomao

def isPrime(n):        #判断一个数是否为素数
    if n<=1:
        return False
    i=2
    while i*i<=n:
        if n%i==0:
            return False
        i+=1
    return True
num=int(input().strip())
p=[]
for i in range(num+1):   #生成素数列表
    if isPrime(i):
        p.append(i)
c=0
for i in range(len(p)):  #遍历素数列表
    j=i                   #从第i个加起
    tmp=[]
    tmp.append(p[j])
    while j+1<len(p) and sum(tmp)< num:
        j=j+1
        tmp.append(p[j])
    if sum(tmp)==num:
        c=c+1
print(c)

1.生成素数列表

2.累加素数列表

编辑于 2021-05-19 20:27:01 回复(0)

牛客12312341

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+100;
int prime[N];
int cnt=0;
int vis[N];
//质数筛
void init(int n){
    for(int i=2;i<=n;i++){
        if(vis[i]==0){
            prime[++cnt]=i;
        }
        for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}

int sum[N];

int main(){
    int n;
    cin>>n;
    int ans=0;
    init(n);
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+prime[i];//前缀和
    for(int len=1;len<=cnt;len++){
        for(int i=1;i+len-1<=cnt;i++){  //枚举左右端点判断胰腺癌即可
            int j=i+len-1;
            if(sum[j]-sum[i-1]==n) ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

发表于 2021-05-11 16:10:49 回复(0)