在C中打印复合数字的最大素数因子

我正在解决一个难题，其中我需要查找用户输入的复合数字的最大素数因子。我想到了一些东西，并试用过它，但它无法检测到复合数字因素中最大的主要因素。在C中打印复合数字的最大素数因子

我在下面追加我的代码，如果有人能帮我找到最大的素数，我会很感激。其中的因素和打印它。

// 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); 
}

来源

2010-08-12 Arun

我不明白。做这样的难题就是为了让你获得解决问题的技巧。让别人去做是完全没有意义的。 – 2010-08-12 17:27:14

~~诀窍是，找到最小素因子，并通过划分它的合数 c，以获得最大的主要因素。~~

诀窍是找到最小的因子F（从2开始），其中C/F是素数。然后，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的平方根停止。但是，在<math.h>中的sqrt()函数在您的情况下工作有点麻烦，因为它适用于浮点数，而不是整数。

来源

2010-08-12 16:35:52

只有当c恰好有两个素数因子时，这才有效 – 2010-08-12 16:37:17

这只是找到最大的因子，因为最小的因子总是质数。 – 2010-08-12 16:49:20

哎呀，谢谢你指出。固定。 – 2010-08-12 16:54:26

在你的内部循环，你设置b = i如果有确实存在许多是i没有一个因素。您需要设置b = i如果不存在存在是的因子i的因子。

（由“数量”，我的意思当然是“2和sqrt(i)之间的整数”）

来源

2010-08-12 16:39:50

要找到因式分解，你通常会发现2和的sqrt（N）之间的所有因素。你会将这些复合材料除以每一个来获得其余的因素。然后递归找出每个人的主要因素。

完成后，您将获得所有主要因素的列表。获得列表中最大的项目应该相当简单。

来源

2010-08-12 16:45:16

“然后递归找出每个这些的主要因素” - 不声音正确 – 2010-08-12 16:50:47

我认为他的意思是递归地申请出去更多的因素，由此产生的较小的数字。例如，如果输入是52，则可以取出一个2，并且26仍然取出另一个2，如52 = 4 X 13和4 = 2 X 2. – 2010-08-12 16:53:50

@JB：是的 - 这就是我想到的。当我坐下来想一想，我并不完全确定这是正确的做事方式，但正是我想到的...... – 2010-08-12 17:00:07

因式分解是一个经典的数论问题。你可以在数字理论教科书中找到许多分解算法。其中一些可在维基百科上找到http://en.wikipedia.org/wiki/Integer_factorization

来源

2010-08-12 17:18:42 gpepper

嘿，感谢输入的朋友，我解决了一些问题，现在程序打印出合成数字的最大素数，条件是合成数小于52，而对于更高超出此范围的范围，它不打印正确的输出。我追加的代码，请看看你们能不能帮我身边

#include<stdio.h>

无效的主要（）{ INT I，J，B = 2，C; printf（“\ n输入组合编号：”）; 012fscanf（“％d”，& c）; printf（“Factors：”）;

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-12 18:01:57 Arun

正如我想象的程序可以采取两种输入： 1）当复合数较小比52（I可以说与此情况下，本码的交易） 2）当复合数大于52时，较小的超过100 （这种情况下，不进行编码）如果有人可以说明第二部分的代码，这将是伟大的！ – Arun 2010-08-12 18:06:10

在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-17 17:43:53

在C中打印复合数字的最大素数因子

回答

相关问题