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()函数 in<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

因式分解是一个经典的数论问题。您可以在数论教科书中找到许多分解算法。其中一些可在 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 回答
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 回答