首页 > 其他 > 详细

求100内质数的个数

时间:2017-02-02 15:38:32      阅读:235      评论:0      收藏:0      [点我收藏+]
// 求100内质数的个数 非容斥 
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n,sum; 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        if(i%2==0||i%3==0||i%5==0||i%7==0) 
        {
            sum++;
            cout<<i<<" ";
        }//不可能出现既是2的倍数也是3的倍数的情况     
    }
    cout<<endl;
    printf("%d",n-sum+3);//sum是求和数的个数,1既不是质数也不是合数 
    return 0;
}
//容斥原理 
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n,sum; 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        if(i%2==0) sum++;
        if(i%3==0)sum++;
        if(i%5==0)sum++;
        if(i%7==0)sum++;
        if(i%5==0&&i%3==0) sum--;
        if(i%2==0&&i%3==0) sum--;
        if(i%7==0&&i%3==0) sum--;
        if(i%2==0&&i%5==0)sum--;
        if(i%2==0&&i%7==0)sum--;
        if(i%5==0&&i%7==0)sum--;
        if(i%2==0&&i%3==0&&i%5==0) sum++;
        if(i%2==0&&i%3==0&&i%7==0) sum++;
        if(i%7==0&&i%5==0&&i%3==0) sum++;
        if(i%2==0&&i%5==0&&i%7==0) sum++;
        if(i%2==0&&i%3==0&&i%5==0&&i%7==0)  sum--;         
    }
    printf("%d",n-sum+3);//sum是求和数的个数,1既不是质数也不是合数 
    return 0;
}

 

样例
10以内质数个数   4
20以内质数个数   8
30以内质数个数   10
100以内质数个数  25

 

求100内质数的个数

原文:http://www.cnblogs.com/z360/p/6361226.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!