HDU5104-Primes Problem

梦里梦外; 2022-06-03 04:40 203阅读 0赞

# Primes Problem #

## Problem Description ##

Given a number n, please count how many tuple(p1, p2, p3) satisfied that p1<=p2<=p3, p1,p2,p3 are primes and p1 + p2 + p3 = n.

## Input ##

Multiple test cases(less than 100), for each test case, the only line indicates the positive integer *n*(*n*≤10000).

## Output ##

For each test case, print the number of ways.

## Sample Input ##

3

9

## Sample Output ##

0

2

#include <bits/stdc++.h>///Primes Problem
    using namespace std;
    #define N 10005
    int prime[N];
    int q[N];
    int main()
    {
        int i,j,k,n,l=0,sum;
        memset(q,0,sizeof(q));
        prime[0]=0;
        prime[1]=0;
        prime[2]=1;
        for(i=3;i<N;i++)//首先偶数一定不是素数,除了2
        {
            if(i%2)
                prime[i]=1;
            else
                prime[i]=0;
        }
        for(i=3;i<=sqrt(N);i++)
        {
            if(prime[i])
            for(j=i+i;j<N;j=j+i)//当i是素数的时候，i的所有的倍数必然是合数
            prime[j]=0;
        }
        for(k=0;k<10000;k++)
        {
            if(prime[k])
                q[l++]=k;
        }
        while(~scanf("%d",&n))
        {
            sum=0;
            for(int i=0;q[i]<n;i++)
                for(int j=i;q[j]<n-q[i];j++)
                {
                    if(prime[n-q[i]-q[j]]&&n-q[i]-q[j]>=q[j])
                    {
                        sum++;
                    }
                }
            printf("%d\n",sum);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，203人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 1016 Prime Ring Problem（dfs）

Prime Ring Problem Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K

亦凉/ 2024年02月17日 19:45/ 0 赞/ 25 阅读

相关 Prime Ring Problem

A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into

女爷i/ 2022年06月12日 02:27/ 0 赞/ 238 阅读

相关 hdu 1016 Prime Ring Problem

Prime Ring Problem Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K

本是古典何须时尚/ 2022年06月12日 02:08/ 0 赞/ 201 阅读

相关 HDU 1016 Prime Ring Problem【深搜练习】

Prime Ring Problem Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K

旧城等待，/ 2022年06月05日 05:45/ 0 赞/ 147 阅读

相关 HDU5104-Primes Problem

Primes Problem Problem Description Given a number n, please count how many tu

梦里梦外;/ 2022年06月03日 04:40/ 0 赞/ 204 阅读

相关 HDU 1016 Prime Ring Problem

Problem Description A ring is compose of n circles as shown in diagram. Put natural num

港控/mmm°/ 2022年05月29日 13:54/ 0 赞/ 195 阅读

相关 HDU-1016 Prime Ring Problem (DFS)

Prime Ring Problem Problem Description A ring

客官°小女子只卖身不卖艺/ 2022年05月19日 00:26/ 0 赞/ 162 阅读

相关 Prime Ring Problem

Prime Ring Problem A ring is compose of n circles as shown in diagram. Put natural nu

小灰灰/ 2022年05月16日 09:06/ 0 赞/ 194 阅读

相关 HDU 1016 Prime Ring Problem

原题目链接[HDU1016][] -------------------- 分类 HDU 素数 DFS -------------------- 题意

分手后的思念是犯贱/ 2022年04月16日 05:54/ 0 赞/ 220 阅读

相关 HDU 1016 Prime Ring Problem

/ A ring is compose of n circles as shown in diagram. Put natural number 1, 2, .

╰半橙微兮°/ 2021年12月20日 02:15/ 0 赞/ 216 阅读