복합 번호의 가장 큰 소수 요소 찾기 (

Question

)

복합 숫자를 입력으로 사용합니다. 나는 모든 요소와 그 수의 가장 큰 소수 요소를 인쇄하고 싶습니다. 다음 코드를 작성했습니다. 번호 51까지 완벽하게 정상적으로 작동합니다. 그러나 51보다 큰 숫자가 입력되면 잘못된 출력이 표시됩니다. 코드를 수정하려면 어떻게해야합니까?

#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=1; j<=i; j++) 
    { 
    if(i%j > 0) 
    { 
    b = i; 
    } 
    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 1

당신은 대신 상대 소수 2,3에 대한 계산하는, 코드가 주어진 수의 모든 소수를 발견 있도록 코딩해야하고, 즉 5. 당신의 코드는 작업 할 수 있습니다 계산하는 숫자는 소수이거나 2, 3 또는 5의 배수입니다. 그러나 7, 11, 13, 17, 19도 소수입니다. 따라서 코드는 특정 숫자의 모든 요소를 ​​찾아서 간단히 작동해야합니다. 더 이상 나눌 수없는 가장 큰 요소를 반환합니다.

Answer 2

나는 배우기 위해 이것을하고 있다고 가정하기 때문에 힌트를주지 않기를 바랍니다.

실패한 숫자에 알고리즘을 적용하는 것으로 시작하겠습니다. 오류가있는 위치가 표시됩니까?

Answer 3

이것은 약간의 스포일러이므로, 이것을 스스로 해결하고 싶다면 아직 읽지 마십시오. :) 나는 연속 순으로 힌트를 제공하기 위해 노력할 것이다, 그래서 당신은 순서대로 각각의 힌트를 읽을 수 있고, 더 많은 힌트를 필요로하는 경우 등, 다음 힌트에

힌트 # 1 이동 : 제수 인 경우 을 n의 약수, n/제수는 또한 n의 약수입니다. 예를 들어, 나머지가 0 2분의 100 = 50이므로 2 (100)의 약수는하지만도 50은 100

힌트 # 2 주어 힌트 # 1, 이것이 수단의 약수 인 것을 의미 우리가 i = 2에서 i * i까지 반복 할 수 있다는 것입니다. < = n 소수 요소를 확인할 때입니다. 예를 들어 숫자 100을 확인하는 경우 힌트 # 1을 사용하여 모든 요소를 ​​얻을 수 있기 때문에 10 (10 * 10은 < = 100)으로 루프하면됩니다. 즉 :

100/2 = 50, so 2 and 50 are factors 
100/5 = 20, so 5 and 20 are factors 
100/10 = 10, so 10 is a factor 

힌트 # 3 우리는 N에 대한 주요 요인에 대한 관심 때문에, 단지, N의 첫 번째 요소를 찾아 제수 호출에 충분한, 그리고 우리가 반복적으로 다른 요인을 찾을 수 있습니다 n/제수의 경우. sieve 접근 방식을 사용하고 요인을 찾아 내면서 요인을 표시 할 수 있습니다. C에서

힌트 # 4 샘플 솔루션 :

bool factors[100000]; 

void getprimefactors(int n) { 
    // 0 and 1 are not prime 
    if (n == 0 || n == 1) return; 

    // find smallest number >= 2 that is a divisor of n (it will be a prime number) 
    int divisor = 0; 
    for(int i = 2; i*i <= n; ++i) { 
    if (n % i == 0) { 
     divisor = i; 
     break; 
    } 
    } 
    if (divisor == 0) { 
    // we didn't find a divisor, so n is prime 
    factors[n] = true; 
    return; 
    } 

    // we found a divisor 
    factors[divisor] = true; 
    getprimefactors(n/divisor); 
} 

int main() { 
    memset(factors,false,sizeof factors); 
    int f = 1234; 
    getprimefactors(f); 
    int largest; 
    printf("prime factors for %d:\n",f); 
    for(int i = 2; i <= f/2; ++i) { 
    if (factors[i]) { 
     printf("%d\n",i); 
     largest = i; 
    } 
    } 
    printf("largest prime factor is %d\n",largest); 
    return 0; 
} 

출력 :

---------- Capture Output ---------- 
> "c:\windows\system32\cmd.exe" /c c:\temp\temp.exe 
prime factors for 1234: 
2 
617 
largest prime factor is 617 
> Terminated with exit code 0. 

Answer 4

정말,이 (말, 10 만 이하) 작은 숫자이지만 모두 매우 느립니다 . 수의 단지 주요 요인을 찾아보십시오 :

addfactor이 주요 요인의 목록에 요소를 추가하는 매크로의 일종이다

#include <cmath> 

void addfactor(int n) { 
    printf ("%d\n", n); 
} 

int main() 
{ 
    int d; 
    int s; 
    int c = 1234567; 
    while (!(c&1)) { 
     addfactor(2); 
     c >>= 1; 
    } 
    while (c%3 == 0) { 
     addfactor(3); 
     c /= 3; 
    } 
    s = (int)sqrt(c + 0.5); 
    for (d = 5; d <= s;) { 
     while (c % d == 0) { 
      addfactor(d); 
      c /= d; 
      s = (int)sqrt(c + 0.5); 
     } 
     d += 2; 
     while (c % d == 0) { 
      addfactor(d); 
      c /= d; 
      s = (int)sqrt(c + 0.5); 
     } 
     d += 4; 
    } 
    if (c > 1) 
     addfactor(c); 
    return 0; 
} 

. 일단 이것들이 있으면, 당신은 그 숫자의 모든 요소들의 목록을 만들 수 있습니다.

여기에 게시 된 다른 코드 스 니펫보다 훨씬 빠릅니다.10597959011과 같은 무작위 입력의 경우, 제 코드는 2000 비트 연산과 같은 것을 취하고 제수를 재구성하기 위해 1000 비트를 더하는 반면, 다른 것들은 수십억 개의 연산을 사용합니다. 이 경우 '인스턴트'와 1 분의 차이입니다. (반복적 인 방법으로) DCP의 대답에

Answer 5

단순화 :

#include <stdio.h> 
void factorize_and_print(unsigned long number) { 
    unsigned long factor; 
    for(factor = 2; number > 1; factor++) { 
    while(number % factor == 0) { 
     number = number/factor; 
     printf("%lu\n",factor); 
    } 
    } 
} 

/* example main */ 
int main(int argc,char** argv) { 
    if(argc >= 2) { 
    long number = atol(argv[1]); 
    factorize_and_print(number); 
    } else { 
    printf("Usage: %s <number>%<number> is unsigned long", argv[0]); 
    } 
} 

참고 : 제대로 ARGV의 수를 못하고 여기에 숫자 분석 버그가 있습니다.