【アルゴリズムノート5.5小節-素因数分解】問題C:素因数の個数

タイトルの説明
正の整数N(N>1)の素因数の個数を求める.
同じ質量係数は繰り返し計算する必要がある.120=2*2*2*3*5のように、5つの素因数がある.
入力
複数組のテストデータがある可能性があり、各組のテストデータの入力は正の整数Nである(1
しゅつりょく
データのセット毎に、Nの素因数の個数を出力する.
サンプル入力

120
200

サンプル出力

5
5

ヒント
方法1:
素数テーブルを印刷して1つずつ検索します.
注意1はNの素因数ではない.Nが素数であれば、NはNの素因数である.

#include
#include
#include
int p[1000001];
int a[1000001];
void Isprime()
{
    int k=0;
    memset(p,0,sizeof(p));
    for(int i=2; i<=1000000; i++)
    {
        if(p[i]==0)
        {
            a[k++] = i;
            for(int j=i+i; j<1000000; j+=i)
                p[j] = 1;
        }
    }
}
int main()
{
    int n;
    Isprime();
    while(scanf("%d",&n)!=EOF)
    {
        int ans = 0;
        int sqr = (int)sqrt(1.0*n);
        for(int i=0; a[i]<=sqr; i++)
        {
            if(n%a[i]==0)
            {
                while(n%a[i]==0)
                {
                    ans++;
                    n/=a[i];
                }
            }
            if(n==1) break;
        }
        if(n!=1)
            ans++;
        printf("%d
", ans);
    }
}

 
方法2:(牛客網から)
コメントエリアの不思議な解法:
作者:misiyuリンク:https://www.nowcoder.com/questionTerminal/20426b85f7fc4ba8b0844cc04807fbd9出典:牛客網はいずれの合数もそれより小さい質量数で除去できるからだ.だから私たちがこの与えられた数を小さい質量数で分解すると、私たちはすでに彼の合数因子を分解しました.あるいは反対側から言えば、合数aがこの数Mを除去することができる場合、j=aの前に質量pがあるべきであり、プログラムの中でMを除去できる数はすべて質量数であることは明らかである.

#include
#include
#include
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int ans = 0;
        int sqr = (int)sqrt(1.0*n);
        for(int i=2; i<=sqr; i++)
        {
            if(n%i==0)
            {
                while(n%i==0)
                {
                    ans++;
                    n/=i;
                }
            }
            if(n==1) break;
        }
        if(n!=1)
            ans++;
        printf("%d
", ans);
    }
}