素因数 種類 カウント

Question

###やりたい事
標準入力から正整数 n（ 0 ＜ n ＜ 2147483648 ）を読み取り、n の素因数が何種類あったかを出力するプログラムの作成

#include <stdio.h>

int main(void){

    int n,c;
  
    scanf("%d",&n);
 //   while (n%2==0) ??
 //   c++; ??
    }
    printf("%d\n",c);
    return 0;
}

Comments

[episteme]

やりたい事はわかりました。
質問はなんですか?

[ta-9]

2で割り切れるだけ割る→3で割り切れるだけ割る→．．．割れなくなったら
割れた回数ではなく割った素数の種類をカウントしたいのですが、どうコードを書けばよいのか
教えて頂きたいです。
(while文？for文？を使用？）

[episteme]

それをナゼ質問に書かない?

Answer 1

こんなんで。

#include <stdio.h>
int main()
{
    int f[11] = { 0 };
    int i, n, c;
    scanf("%d", &n);
    for (i = 2, c = 0; n > 1; i++) {
        if (n % i == 0) {
            do
                n /= i;
            while (n % i == 0);
            f[c] = i;
            c++;
        }
    }
	printf("%d\n\n",c);
    for (i = 0; f[i]; i++)
        printf("%d\n", f[i]);
    return 0;
}

こんなんでいいかな？

#include <stdio.h>
int main()
{
    int f[9];
    int i, n, c = 0;
    scanf("%d", &n);
    if (n % 2 == 0) {
        do
            n /= 2;
        while (n % 2 == 0);
        f[c] = 2;
        c++;
    }
    if (n % 3 == 0) {
        do
            n /= 3;
        while (n % 3 == 0);
        f[c] = 3;
        c++;
    }
// 超過するのを忘れていたので、もうちょっと大きな型にしてください。
    for (i = 5; (unsigned)i * i <= n; i += 4) {
        if (n % i == 0) {
            do
                n /= i;
            while (n % i == 0);
            f[c] = i;
            c++;
        }
        i += 2;
        if (n % i == 0) {
            do
                n /= i;
            while (n % i == 0);
            f[c] = i;
            c++;
        }
    }
    if (n > 1) {
        f[c] = n;
        c++;
    }
    printf("%d\n\n", c);
    for (i = 0; i < c; i++)
        printf("%d\n", f[i]);
    return 0;
}

Comments

[ta-9]

ご回答有難うございます。
n が素数だと言うことを知るのに「 n までのすべての整数で割ってみる」以外に何か方法はありますでしょうか？桁数が大きくなってくるととても時間が掛かってしまい。。。
(例えば2147483647を計算するのに2147483647回計算が必要という意味です)

[episteme]

たとえば:
「√pまでのすべての素数で割れなければpは素数」だから
1～pまでの素数表を基に1～p*pまでの素数表が作れる。
これをn回繰り返せば1～2^nまでの素数表が作れる。

[PingHermit]

素数重視なら、epistemeさんが書いている方法(たぶんエラトステネスの篩)で。
素因数重視なら、最初にテーブル作るのはちょっとお勧めできません。

[PingHermit]

いや、epistemeさんだから、何かいい方法知ってるのかも。
作例お願いします>episteme

[ta-9]

ご回答有難うございます。
1度使用した2や3を格納しておき、何度も同じ計算をしないという方法と理解しました。
(間違っていたら申し訳ありません)
ただ、正しい出力結果は得られるのですが2147483647の計算の時に膨大な時間が掛かって
しまう為、ほかにもっと短縮する方法が無いか考えてみます。

[PingHermit]

チョンボしてました。修正してください。

[PingHermit]

この数値なら、単純に unsigned だけでもカバーできるみたいです。

[ta-9]

ご回答有難うございます。
とても短縮できました。

Answer 2

ひんと

 if ( n が p で割りきれる ) {
   ++count;
   n を p で割れるだけ割る
 }

を、p = 2, 3, 5, 7, 11 .... (√n以下の素数)に対して行う。

Comments

[ta-9]

う～ん、こんな感じ．．．？
if(n%p==0){
count++;
while(n%p==0)
p++;
}

[episteme]

知らんがな。やってみたらええやん。