在C中打印複合數字的最大素數因子

Question

我正在解決一個難題，其中我需要查找用戶輸入的複合數字的最大素數因子。 我想到了一些東西，並試用過它，但它無法檢測到複合數字因素中最大的主要因素。

我在下面追加我的代碼，如果有人能幫我找到最大的素數，我會很感激。其中的因素和打印它。

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

Answer 1

訣竅是，找到 最小素因子，並通過劃分它的合數 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()函數在您的情況下工作有點麻煩，因爲它適用於浮點數，而不是整數。

Answer 2

在你的內部循環，你設置b = i如果有確實存在許多是i沒有一個因素。您需要設置b = i如果不存在存在是的因子i的因子。

（由「數量」，我的意思當然是「2和sqrt(i)之間的整數」）

Answer 3

要找到因式分解，你通常會發現2和的sqrt（N）之間的所有因素。你會將這些複合材料除以每一個來獲得其餘的因素。然後遞歸找出每個人的主要因素。

完成後，您將獲得所有主要因素的列表。獲得列表中最大的項目應該相當簡單。

Answer 4

因式分解是一個經典的數論問題。你可以在數字理論教科書中找到許多分解算法。其中一些可在維基百科上找到http://en.wikipedia.org/wiki/Integer_factorization

Answer 5

嘿，感謝輸入的朋友，我解決了一些問題，現在程序打印出合成數字的最大素數，條件是合成數小於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); 

}

Answer 6

在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 

我做了什麼檢查素性是整齊的平方根技術。