a740

輸入說明 ：

每行一个正整数，x<20000000, 以EOF为结束

輸出說明 ：

对应的因数和

這題跟b763很像都是先建質數表

但是這題質數表的型態要用bool,用int的話,會超出記憶體限制

#include<stdio.h>
#include<string.h>
#include <vector>
using namespace std;
bool  P[20000000];
vector<int> p;

int main()
{
    memset(P,1,sizeof(P));

     long long int i;
     long long int j;

    for(i=2;i<20000000;i++)
    {
        if(P[i]) 
        {
            p.push_back(i);
            for(j=i*i;j<20000000;j+=i)
                P[j] = false;
        }
    }
    int n; 
    long long int  sum;

    while( scanf("%d", &n) != EOF )
    {
        sum = 0;

        for(i=0; i<p.size(); i++)
        {
            while( n%p[i] == 0 ) 
                n/= p[i],sum +=p[i];
            if(n==1) break;
        }

        if(n==1) printf("%lld\n", sum);
        else printf("%lld\n", sum+n);
    }
}