（质因子打表记录素数的位置）HDU Largest prime factor

传送门：http://acm.split.hdu.edu.cn/showproblem.php?pid=2136

利用素数打表的筛选法

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;



int a[1000000];
int main(){

   int ans,k=0;
   memset(a,0,sizeof(a));
   for(int i=2;i<1000000;i++)
    {
       if(a[i]==0){
       k++; //用k标记素数在表中的位置
    for(int j=i;j<1000000;j+=i){
       a[j]=k;}

   }
   }
    while(~scanf("%d",&ans))//题目没有给结束尾，切记要用~符号或者EOF
    {
        cout<<a[ans]<<endl; //把素数的位置打印出来
    }
    return 0 ;
   }

 

下面是质因子打表的常规方法

void init_prime()
{
    int i, j;
    for(i = 2;i <= sqrt(1000002.0); ++i)//sqrt内为质因子
    {
        if(!prime[i])
            for(j = i * i; j < 1000002; j += i)
                prime[j] = 1;
    }
    j = 0;
    for(i = 2;i <= 1000002; ++i)
        if(!prime[i])
            prime[j++] = i;
}

把质数全部存在prime数组中 从0开始

void set()
{   
    l=0;
    int i,j;
    memset(prime,0,sizeof(prime));
    for(i = 2; i<N; i++)
    {
        if(prime[i])
            continue;
        for(j = i+i; j<N; j+=i)
            prime[j] = 1;
        s[l++] = i;
    }
}

素数表的构建：

bool isPrime(int k)
{
    for (int i = 0; i < count; i++) {
        if (k % prime[i] == 0) {
            return false;
        }
    }
    return true;
}

int main()
{
    //开始构建素数表
    for (int i = 2; i <= 10000; i++) {
        if (isPrime(i)) {
            prime[count] = i;
            count++;
        }
    }