primelist.cpp

一些ACM题目的解答,主要是soj和poj的

#include<stdio.h>
#include<math.h>

const int MAX = 1000001;

int a[MAX];

int next(int i)
{
    int j=i+1;
    while(a[j]==1&&j<MAX)
        j++;
    return j;
}
void primelist(void)
{
    int i,j,k;
    for(i=2;i*i<MAX;i=next(i))
    {
        for(j=i;j*i<MAX;j=next(j))
        {
            for(k=i*j;k<MAX;k*=i)
            {
                a[k]=1;
            }
        }
    }
    for(i=2,j=0;i<MAX;i++)
    {
        if(!a[i])
            a[j++]=i;
    }
}