| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
ADSL如何秒变专线,公网IP盒子了解一下千里之行 始于足下
共有 1072 人关注过本帖, 1 人收藏
标题:【求助】c++统计质数问题怎么做?
只看楼主 加入收藏
asdfaad
Rank: 1
来 自:重庆
等 级:新手上路
帖 子:25
专家分:0
注 册:2018-12-21
结帖率:57.14%
  已结贴   问题点数:20  回复次数:4   
【求助】c++统计质数问题怎么做?
统计质数(必做)
(时间限制:1000ms 内存限制:65536KB)
统计
描述
小美同学有一组大于零的整数,想要调出其中的质数来,请你编程帮她实现吧。
输入:第一行有一个大于零的整数n(0<n<100),表示小美有n个数。第二行依次输入n个正整数。
输出:这n个数当中的质数。
要求:使用函数调用


输入
第一行有一个大于零的整数n(0<n<100),表示小美有n个数。第二行依次输入n个正整数。

输出
这n个数当中的质数。

难度
一般

输入示例
4
1 2 3 4

输出示例
2 3
搜索更多相关主题的帖子: 统计 质数 整数 输入 个数 
2019-01-25 12:18
ZJYTY
Rank: 7Rank: 7Rank: 7
等 级:黑侠
威 望:3
帖 子:88
专家分:658
注 册:2018-12-20
  得分:7 
程序代码:
#include<iostream>
#include<vector>
#include<time.h>

using namespace std;

class PrimePalindrome
{
public:
    void PrimeNumbers();
    void showNumbers();
    void inputNum();
private:
    int numbers;
    vector<int> inPut;
    vector<int> Prime;
};

void PrimePalindrome::PrimeNumbers()
{
    int a = 0;
    int i;
    vector<int>::iterator itr = inPut.begin();
    for (itr; itr != inPut.end(); ++itr)
    {
        for (i = 2; i <= (*itr); ++i)
        {
            if ((*itr) % i == 0)
                break;
        }
        if (i == (*itr)){
            Prime.push_back(*itr);
        }
    }
}

void PrimePalindrome::showNumbers()
{
    cout << "质数列表:" << endl;
    for (vector<int>::iterator itr = Prime.begin(); itr != Prime.end(); ++itr)
    {
        cout << *itr << endl;
    }
}
void PrimePalindrome::inputNum()
{
    int inputNumber;
    cout << "Input the number of number : ";
    cin >> numbers;
    while (!getchar());
    for (int i = 0; i < numbers; ++i)
    {
        cin >> inputNumber;
        while (!getchar());
        inPut.push_back(inputNumber);
    }
}

int main()
{
    clock_t start, finish;
    double totaltime;

    PrimePalindrome pp;
    pp.inputNum();
    start = clock();

    pp.PrimeNumbers();
    pp.showNumbers();

    finish = clock();
    totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
    cout << "\n此程序的运行时间为" << totaltime << "秒!" << endl;
    getchar();
}


附件: 您没有浏览附件的权限,请 登录注册

-------------------------------若有不当之处,敬请谅解-------------------------------
2019-01-25 13:48
lyb661
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:18
帖 子:47
专家分:83
注 册:2018-12-12
  得分:7 
bool isPrime(int n)
{
    for(int i=2;i<=(int)sqrt(n);i++){
        if(n%i==0)
            return false;
    }
    return true;
}
2019-01-25 19:25
幽竹烟雨
Rank: 2
来 自:SunGalaxy
等 级:论坛游民
威 望:3
帖 子:40
专家分:82
注 册:2018-11-9
  得分:7 
建议不要搞太多对新人不友好的东西,下面上我的代码(建议楼主好好看看,不要为抄答案而忽略注释,判素这个函数真的很基础又很重要,一定要好好理解哦~)

#include<bits/stdc++.h>//万能头文件,不过并不包括<windows.h>库等好玩的东西
using namespace std;
int a[1000000];//数组是不是开太大了?
bool lele(int n)//判素神器
{
    if(n==1||n==0) return false;//要考虑 0、1不是素数的情况
    for(int i=2;i<=sqrt(n);i++)//进行列举排除,sqrt(n)是取n的平方根,提高效率
    {
        if(n%i==0) return false;//如果i能被n整除,说明i是n的因数,n就不是素数,返回假
    }
    return true;//循环结束后,说明n是素数,返回真
}
int main()
{
    ios::sync_with_stdio(false);//个人习惯,您可以选择注释掉它
    int n,i,o=0;
    cin>>n;
    for(i=1;i<=n;i++)
    cin>>a[i];//输入这几个数
    for(i=1;i<=n;i++)
    {
        if(lele(a[i]))//逐一进行判断,如果满足条件(是素数),就输出
        {
            if(o==0)//为了防止输出后面多了空格,我是这样处理的
            {
                cout<<a[i];
                o++;
            }
            else cout<<" "<<a[i];
        }
    }
    return 0;//完美地结束
}
2019-01-30 22:17
流照君
Rank: 2
等 级:论坛游民
帖 子:66
专家分:74
注 册:2018-5-7
  得分:0 
看了楼上的觉得有必要贴一下自己的代码了;
因为楼上的都是一个个判断;
埃式素数筛选才是时间复杂都最快的
楼主可以去百度一下
#include<iostream>
#include<string.h>
using namespace std;
#define MAX_N 100000
bool is_prime[MAX_N];
int prim[MAX_N];

int sieve(int n)
{
   int num=0;
    for(int i=2;i<=n;i++)
        is_prime[i]=true;
    is_prime[0]=is_prime[1]=false;
    for(int i=2;i<=n;i++)
    {
        if(is_prime[i])
        {
            prim[num++]=i;   
            for(int j=2*i;j<=n;j+=i)
                is_prime[j]=false;
        }
    }
    return num;
}
int main()
{
    int N;
    cin>>N;
   
        memset(prim,0,sizeof(prim));
         for(int i=0;i<sieve(N);i++)
    cout<<prim[i]<<endl;
   
}
2019-02-28 22:26







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.026372 second(s), 9 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved