C 코드가 영원히 계속 실행됩니다. *

Question

C에서 거대한 숫자의 가장 큰 소수 요소를 찾으려고합니다. 100 또는 10000과 같은 작은 숫자는 제대로 작동하지만 실패합니다. 실패로 인해 계속 유지됩니다. 실행 및 실행 내 core2duo 및 i5에서 수십 분 동안 매우 큰 target 숫자입니다 (대상 번호에 대한 코드 참조). 내 알고리즘이 맞습니까?

저는 C가 생소하고 큰 숫자로 인해 어려움을 겪습니다. 내가 뭘 원하는 건 정정이나 지침이 아닙니다 bignum 바인딩 및 물건 (아직 나는 시도했지만 꽤 확실한)와 파이썬을 사용하여 할 수있는 솔루션이 아니지만 아니면 내가 몇 가지 작은 실수를했을 수도 있습니다 실현 너무 피곤, 어쨌든 여기에 내가 쓴 코드 :

#include <stdio.h> 
// To find largest prime factor of target 
int is_prime(unsigned long long int num); 

long int main(void) { 
    unsigned long long int target = 600851475143; 
    unsigned long long int current_factor = 1; 
    register unsigned long long int i = 2; 
    while (i < target) { 
     if ((target % i) == 0 && is_prime(i) && (i > current_factor)) { //verify i as a prime factor and greater than last factor 
      current_factor = i; 
     } 
     i++; 
    } 
    printf("The greates is: %llu \n",current_factor); 
return(0); 
} 


int is_prime (unsigned long long int num) { //if num is prime 1 else 0 
    unsigned long long int z = 2; 
    while (num > z && z !=num) { 
     if ((num % z) == 0) {return 0;} 
     z++; 
    } 

return 1; 
} 

Answer 1

6 천억 개의 반복은 아무런 사소한 시간도 걸릴 것입니다. 이 점을 상당히 줄여야합니다.

는 여기에 힌트 : 임의의 정수 값 x을 감안할 때, 우리는 y가 요소임을 발견 할 경우, 우리는 암시 x/y도 요소임을 발견했습니다. 즉, 요소는 항상 쌍으로됩니다. 따라서 중복 작업을 수행하기 전에 얼마나 반복해야하는지에 한계가 있습니다.

그 한도는 무엇입니까? 자, y이 x/y보다 커질 교차점은 무엇입니까?

외부 루프에이 최적화를 적용하면 코드 실행 시간이 is_prime 함수에 의해 제한된다는 것을 알 수 있습니다. 하지만 물론 비슷한 기술을 적용 할 수도 있습니다.

Answer 2

수의 제곱근 때까지 반복함으로써, 우리는 모든 요인이다 얻을 수 있습니다 (factor 및 N/factor 및 factor<=sqrt(N)을).. 이 작은 아이디어 하에서 해결책이 존재합니다. 확인하는 요소가 sqrt(N)보다 작 으면 sqrt(N)보다 큰 해당 요소가 있습니다. 따라서 sqrt(N)까지만 확인하면 남은 요소를 얻을 수 있습니다.

여기에서는 프라임 찾기 알고리즘을 명시 적으로 사용할 필요가 없습니다. 인수 분해 논리 자체는 목표가 소수인지 여부를 추론합니다. 그래서 남은 것은 pairwise 요인을 확인하는 것입니다.

unsigned long long ans ; 
for(unsigned long long i = 2; i<=target/i; i++) 
    while(target % i == 0){ 
     ans = i; 
     target/=i; 
    } 

if(target > 1) ans = target; // that means target is a prime. 
//print ans 

^{편집 : 점은 (chux) 추가 할 - 이전 코드에서 i*i을 우리가 i<=target/i를 사용하면 피할 수 있습니다 오버 플로우가 발생할 수 있습니다. 반올림 오류가 발생하기 쉬운 정수 연산 더블 수학의 혼합 -}

^{또 다른 선택은 현명한 선택이 있기 때문에하지}

다음

unsigned long long sqaure_root = isqrt(target); 
for(unsigned long long i = 2; i<=square_root; i++){ 
... 
} 

이 sqrt의 사용에보다주의해야하는 것 . 대답은 6857 될 것 지정한 대상

.

Answer 3

is_prime은 다른 소수에 대해서만 num을 테스트해야한다는 점에서 닭고기 및 달걀 문제가 있습니다. 따라서 3의 배수이기 때문에 9를 검사 할 필요가 없습니다.

은 소수 배열을 유지 관리 할 수 ​​있으며 새 num이 테스트 될 때마다 배열에 추가 할 수 있습니다. num isr 배열의 각 소수에 대해 테스트되고 배열의 소수에서 나눌 수없는 경우 자체가 소수이며 배열에 추가됩니다. Aray는 malloc'd와 relloc'd가 될 필요가 있습니다. 목표가있는 소수의 수를 계산할 수있는 형식이 없다면 (나는 그러한 수식이 존재하지 않는다고 생각합니다).

EDIT : 대상을 테스트 할 소수의 수 600,851,475,143은 약 7,500,000,000이고 테이블의 메모리가 부족할 수 있습니다.

다음과 같은 접근 방식은 적응 될 수

• 는 상기 무력을 사용하는

• 상기 소수위한 unsigned long long int를 사용 UINT_max

• 의 소수까지 unsiged int를 사용 특정 메모리 소비.

UINT_MAX는 4294967295로 정의하고 주위 천억까지 소수를 포함 할 7.5 * 4 = 30GB

참조에게 또한 The Prime Pages 비용 것입니다.

Answer 4

아무 잘못 없다, 그냥 예를 들어, 최적화를 필요로 : 당신은 내가 할 솔루션을하지 않기 때문에

이

int is_prime(unsigned long long int num) { 
    if (num == 2) { 
     return (1);    /* Special case */ 
    } 
    if (num % 2 == 0 || num <= 1) { 
     return (0); 
    } 
    unsigned long long int z = 3; /* We skipped the all even numbers */ 
    while (z < num) {    /* Do a single test instead of your redundant ones */ 
     if ((num % z) == 0) { 
      return 0; 
     } 
     z += 2;      /* Here we go twice as fast */ 
    } 
return 1; 
} 

이 또한 큰 다른 문제는 당신이 방법을 찾을 수있다 (Z < NUM) 동안 만 그것을 최적화하고, 유사하게 첫 번째 기능을 스스로 알아보십시오.

EDIT : 다른 누군가가 나보다 50 초 앞선 primes 솔루션의 배열 목록을 게시했지만 당신이 초보자이고 조작이 쉬운 배열을 처음부터 쉽게 사용할 수 있기 때문에 쉬운 솔루션을 제공하기로했습니다. 포인터와 물건을 배우십시오).

Answer 5

코드 2 큰 문제

while (i < target) 루프가 매우 비효율적이다

1. 있습니다. 요인을 발견하면 target을 target = target/i;으로 줄일 수 있습니다. 또한, 인자 i은 여러 번 발생할 수 있습니다. 수정되지 않음.

2. is_prime(n)은 매우 비효율적이다. 그것의 while (num > z && z !=num)은 n 시간 루프 수 있습니다. 여기에서도 몫을 사용하여 반복을 sqrt(n) 번으로 제한합니다.

   int is_prime (unsigned long long int num) { 
       unsigned long long int z = 2; 
       while (z <= num/z) { 
       if ((num % z) == 0) return 0; 
       z++; 
       } 
       return num > 1; 
   }