怎么用筛选法输出100之内的素数？ - 编程论坛

#2

hahayezhe2010-10-19 08:57

在if块里写个break;

#3

xinyuan542010-10-19 09:00

#include "stdafx.h"
#include<iostream>
using namespace std;

int main()
{
    int a[100],i,j;
    for(i=0;i<100;i++)
    {
        a[i]=i+1;
    }
    for(i=0;i<100;i++)
      {
          for(j=2;j<i+1;j++)
            {
                if(a[i]%j==0)
                    break;
                if(i==j)
                cout<<a[i]<<endl;
            }
    }
return 0;
}

#4

孙优2010-10-19 10:16

这是用C写的，用VC也能编译，你可以看一下

#include <stdio.h>
void main()
{
    int i,j,a[100]={0},f,n=0;
    for(i=3;i<100;i++)
    {   f=0;
        for(j=2;j<i;j++)
            if(i%j==0)
               f=f+1;
        if(f!=0)
            a[i-1]=i;
    }
    printf("100以内的素数有");
    for(i=0;i<100;i++)
    {
        if(a[i]!=0)
        {
            n=n+1;
            printf("%d ",a[i]);

        }
        if(n%10==0)
           printf("\n");

}
printf("\n");

}

#5

zfk3052010-10-19 11:24

三楼貌似不用加#include "stdafx.h"吧？

#6

xinyuan542010-10-19 16:47

回复 5楼 zfk305

我用的是VS2008
每个c++都要那个··
不然编译通不过··

#7

xy92932010-10-19 17:32

回复楼主 doofymark

#include<iostream>
using namespace std;

int main()
{
    int a[100],i,j,o=0;
    for(i=0;i<100;i++)
    {a[i]=i+1;}
    for(i=1;i<100;i++)
      {  for(j=2;j<i+1;j++)
            {if(a[i]%j==0) o=1;}
         if(o==0) cout<<a[i]<<endl;
         o=0;
      }
    return 0;}
可以吗？

[ 本帖最后由 xy9293 于 2010-10-19 17:38 编辑 ]

#8

Tveiker2010-10-19 22:50

可以标志啊，比如用b[100]来标示a[100]的每个数是否输出，比如a[44]已输出则b[44]=1,否则b[44]=0;
良好的编程习惯很重要
#include<iostream>
#include<iomanip>
using namespace std;

int main(){
    int a[100],i,j;
    int b[100],count=0;
    for(i=0;i<100;i++){
        a[i]=i+1;
        b[i]=0;    //使数组b的每个元素为0，表示还未输出
    }
    cout<<"被筛出的非素数依次是:"<<endl;
    for(i=0;i<100;i++){
        for(j=2;j<i+1;j++){
            if(a[i]%j==0&&b[i]==0) {
                cout<<setw(3)<<setiosflags(ios::right)<<a[i]<<" ";//加入的代码是设置输出格式的宽3右对齐
                count++;
                b[i]=1;
                if(count%10==0)    //每行10个数
                    cout<<endl;
            }
        }
    }
    cout<<endl;
    return 0;
}

#9

pangding2010-10-19 23:41

筛法筛几亿以内的质数也就是一会的事。你可以先筛好了再输出嘛。
这个程序筛了10亿以内的素数，但速度也不太快，我机子上跑大约要一分半左右的时间。它没有输出，但确实是筛了，如果你想看它筛的结果，就把有注释的地方改成 1 就行了。但要小心使用，它会输出一个 1G 左右的文本文件，跑下来要花大约二分钟左右的时间。
嫌大就把那个 N 改小一点。

程序代码：

#include <stdio.h>
#include <stdlib.h>

#define N 1000000000

int main(int argc, const char *argv[])
{
    int i, j;
    FILE *f = fopen("prime_list.txt", "w");
    if (!f) { perror("fopen"); exit(1); }
    char *flag = (char *)calloc(N, sizeof(char));

    for(i = 2; i < N; ++i) {
        if(flag[i]) continue;
        for(j = 2*i; j < N; j += i)
            flag[j] = 1;
    }

#if 0        // change this to 1, to write to file.
    for(j = 0, i = 2; i < N; ++i) {
        if(flag[i] == 0) fprintf(f, "%10d: %d\n", ++j, i);
    }
#endif

    fclose(f);

    return 0;
}

#10

doofymark2010-10-20 06:21

回复 3楼 xinyuan54

我明白了...if(i==j) cout<<a[i]<<endl;
这样只有j加到最后一项才会输出了...谢谢啦！

#11

doofymark2010-10-20 06:23

回复 8楼 Tveiker

我明白了...只有b[i]==0的时候才会输出...所以a[i]只能输出一次...
谢谢啦！

#12

doofymark2010-10-20 06:25

回复 9楼 pangding

大师啊...你这东西颇为有些深奥啊...小弟先收着...
对不起啊...实在是有点不知道这个玩意在说什么的感觉...

#13

ybjx19872010-10-20 13:59

int i,j;
bool f;
for(i=3;i<100;i++)
{
    f=true;
    for(j=2;j<sqr(i)+1;j++)
    {
        if(i%j==0)
        {
            f=false;
            break;
        }
    }
    if(f)
    {
        cout<<i<<"  ";
    }
}
感觉这么写会运算快一些，因为少了很多不必要的过程。

#14

pangding2010-10-20 22:09

回复 12楼 doofymark

呵呵，这是我的一个同学在我教了他这个算法之后写的。

算法是把所有素数的倍数从数组里删去。
数组开始的时候里面全是0，然后 i = 2 是素数。j = 2 * i 是 4，4 的地方被标记成 1，就是合数。之后 j += i，就是让 j 一直取 2i, 3i, 4i, .... 这些都是 i 的倍数，因此是合数。然后 i 往后找第一个是 0 的值，因为这个值不是比它小的所有素数的倍数，因此也是素数，然后 j 再把这个数的倍数划去。最后表里是 0 的数，就是素数。打印出来就行了。

刚才看才发现，他申请完内存之后都没试试是不是成功就用了那块内存。这不是个好习惯，大家可以在 calloc 的下一行加一个
if (!flag) { ...... }
访照文件打开下面的語句处理一下。