1

ユーザーが入力した合成数の最大素因数を見つける必要があるパズルを解いていました。と思ってやってみたのですが、合成数の約数の中で最大の素因数が検出できません。

以下にコードを追加します。誰かがここで最大の素数を検出するのを手伝ってくれたらありがたいです。要因の中で、それを印刷します。

// Accept a composite number from user and print its largest prime factor.

#include<stdio.h>
void main()
{
    int i,j,b=2,c;
    printf("\nEnter a composite number: ");
    scanf("%d", &c);
    printf("Factors: ");

    for(i=1; i<=c/2; i++)
    {
        if(c%i==0)
        {
            printf("%d ", i);
            for(j=2; j<=i/2; j++) //since a numbr cand be divisible by a number greated than its half
            {               if(i%j > 0) 
                    b = i;
                else if(i==3)
                    b = 3;
            }
        }
    }
    printf("%d\nLargest prime factor: %d\n", c, b);
}
4

6 に答える 6

3

秘訣は、最小の素因数を見つけ、それで合成数を割っcて最大の素因数を取得することです。

秘訣は、C / Fが素数である最小の因子F（2から始まる）を見つけることです。そうすると、C/FがCの最大の素因数になります。

編集：あなたもすべての要因をリストしたいようです。i問題は、素数性をテストする内側のループで、何でも割り切れる数の最大の素数をに設定することです。言い換えれば、次のようなことを試してください。

is_prime = true;

for (j = 2; j <= x / 2; j++) {
    if (i % j == 0)
        is_prime = false;
}

if (is_prime)
    largest_prime = x;

xを2で割った値よりも早く停止できることに注意してください。xの平方根で停止できます。ただし、のsqrt()関数<math.h>は整数ではなく浮動小数点数で機能するため、この場合は少し面倒です。

于 2010-08-12T16:35:52.200 に答える
1

内側のループでは、 の因数ではない数値が存在するかb = iどうかを設定しています。の因数となる数が存在しない場合に設定する必要があります。ib = ii

2(「数値」とsqrt(i)は、もちろん「 ～ の間の整数」を意味します)

于 2010-08-12T16:39:50.337 に答える
1

素因数分解を見つけるには、通常、2 と sqrt(N) の間のすべての因数を見つけます。コンポジットをそれらのそれぞれで割って、残りの要因を取得します。次に、再帰してそれぞれの素因数を見つけます。

完了すると、すべての素因数のリストが表示されます。リスト内の最大のアイテムを取得することは、かなり簡単です。

于 2010-08-12T16:45:16.467 に答える
0

入力の友人に感謝します。私は何かを解決し、合成数が52未満の場合、プログラムは合成数の最大の素因数を出力しますが、これを超える高い範囲では正しい出力を出力しません. コードを追加しています。皆さんが私を助けてくれるかどうかを確認してください

#include<stdio.h>

void main() { int i,j,b=2,c; printf("\n合成数を入力してください: "); scanf("%d", &c); printf("要因: ");

for(i=1; i<=c/2; i++)
{
    if(c%i==0)
    {
        printf("%d ", i);
        for(j=1; j<=i; j++) //since a numbr cand be divisible by a number greated than its half
        {               if(i%j > 0)
                b = i; //b stores the largest prime factor
            if(b%3==0)
                b = 3;
                else if(b%2==0)
                b=2;
              else if(b%5==0)
                b=5;
                }
    }
}


printf("%d\nLargest prime factor: %d\n", c, b);

}

于 2010-08-12T18:01:57.133 に答える
0

因数分解は古典的な数論の問題です。数論の教科書には多くの因数分解アルゴリズムがあります。それらのいくつかは wiki http://en.wikipedia.org/wiki/Integer_factorizationで入手できます

于 2010-08-12T17:18:42.817 に答える
0

Python では、次のようなことができます。

import math
import itertools

# largest prime factor of a composite number
def primality(num):
    for i in range(2,int(math.sqrt(num))+1):
        if num%i ==0:
             return 0
    return 1

if __name__ == '__main__':
    number = 600851475143
    for i in itertools.count(2,1):
            if number%i == 0:
                if number%10 in [7,9,1,3] and primality(number/i):
                    print number/i
                    break

素数性をチェックするために私が行ったことは、きちんとした平方根テクニックです。

于 2012-05-17T17:43:53.797 に答える