Как повысить эффективность моего кода?

Question

Я хочу, чтобы моя программа находила самый большой простой коэффициент числа 600851475143. Например, основными факторами 13195 являются 5, 7, 13 и 29 и 29 - самые большие. В то время как мой код работает, ответ занимает слишком много времени, чтобы появляться даже для гораздо меньших входов, например, 6kk (занимает около 15 секунд. Для 12kk это занимает 37 секунд, поэтому приращения еще хуже, чем линейные), что составляет 100k раз меньше числа, которое я должен использовать в качестве ввода. Ниже мой код, любая помощь, связанная с повышением эффективности кода, будет очень признательна.

#include <stdio.h> 
#include <math.h> 

int main() 
{ 
    long long int number=600851475143; 
    int largest_prime_factor,i,j,k; 
    for (i=1;i<number/2;i+=2){ 
     k=0; 
     j=3; 
     for (j=3;j<=sqrt(i);j+=2){ 
      if (i%j==0){ 
       k++; 
       break; 
       } 
       } 
     if (k==0){ 
      if (number%i==0) 
       largest_prime_factor=i; 
     } 
    } 
    printf("The largest prime factor of 600851475143 is: %d", 
    largest_prime_factor); 
    return 0; 
} 

Answer 1

Вы должны переместить sqrt(i) из цикла for. Он вычисляется в каждом цикле. Также j*j <= i будет намного быстрее, чем j <= sqrt(i).

Существует ошибки в коде: если число является long long int остальными переменными должен быть слишком или условие i<number/2 всегда верно!

Answer 2

В общем, не существует эффективного способа сделать это: https://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity

Есть способы увеличить скорость вашего кода, хотя. Посмотрите на некоторые из алгоритмов в этой статье.

Answer 3

Этот код должен быть довольно быстро и занимает всего несколько миллисекунд для числа 600851475143:

long long int primes[1000]; 
int primesSize = 0; 
long long int primeFactors[100]; 
int primeFactorsSize = 0; 

long long int number = 600851475143ll; 

for (long long int f = 2; f < number/2; ++f) 
{ 
    // Check if f is a prime number 
    int primesIndex = 0; 
    while (primesIndex < primesSize && (f%primes[primesIndex]) != 0) 
     ++primesIndex; 

    if (primesIndex >= primesSize) 
    { 
     primes[primesSize++] = f; 

     // Check if f is a prime factor of number 
     while ((number % f) == 0) 
     { 
      primeFactors[primeFactorsSize++] = f; 
      number /= f; 
     } 
    } 
} 

if (number != 1) 
    primeFactors[primeFactorsSize++] = number; 

Создание списка простых чисел уже нашел ускоряет проверку другого возможного фактора.

Если вы нашли основной коэффициент своего номера, вы разделите свой номер на коэффициент и продолжите с результатом деления. Возможно, это разделение нужно делать несколько раз. Конечным значением в number также является наибольший простой коэффициент.

Предупреждение: Мой код не был протестирован вообще. Я просто убедился, что результат верный для number = 600851475143ll. Также я использую компилятор C++, поэтому вам, возможно, придется внести незначительные изменения.

Для больших number S необходимо реализовать динамическое выделение памяти, по крайней мере для primes массива:

#include <stdlib.h> 
#include <stdio.h> 

int main() 
{ 
    long long int *primes = NULL; 
    int primesSize = 0; 
    int primesCapacity = 0; 
    long long int *primeFactors = NULL; 
    int primeFactorsSize = 0; 
    int primeFactorsCapacity = 0; 

    long long int number = 600851475143ll; 
    number = 13456769ll; 

    for (long long int f = 2; f < number/2; ++f) 
    { 
     // Check if f is a prime number 
     int primesIndex = 0; 
     while (primesIndex < primesSize && (f%primes[primesIndex]) != 0) 
      ++primesIndex; 

     if (primesIndex >= primesSize) 
     { 
      if (primesSize == primesCapacity) 
      { 
       primesCapacity += 1000; 
       primes = (long long int*)realloc(primes, primesCapacity * sizeof(long long int)); 
      } 
      primes[primesSize++] = f; 

      // Check if f is a prime factor of number 
      while ((number % f) == 0) 
      { 
       if (primeFactorsSize == primeFactorsCapacity) 
       { 
        primeFactorsCapacity += 1000; 
        primeFactors = (long long int*)realloc(primeFactors, primeFactorsCapacity * sizeof(long long int)); 
       } 
       primeFactors[primeFactorsSize++] = f; 
       number /= f; 
      } 
     } 
    } 

    if (number != 1) 
    { 
     if (primeFactorsSize == primeFactorsCapacity) 
     { 
      primeFactorsCapacity += 1000; 
      primeFactors = (long long int*)realloc(primeFactors, primeFactorsCapacity * sizeof(long long int)); 
     } 

     primeFactors[primeFactorsSize++] = number; 
    } 

    printf("Last prime factor is %lld", primeFactors[primeFactorsSize-1]); 

    return 0; 
} 

Answer 4

Вам не нужно ехать через весь список. Когда вы найдете один основной фактор, вы факторизуете свой номер и продолжаете работать с тем, что осталось.

Например, возьмите пример: 600 851 475 143. Вы можете быстро найти свой первый основной коэффициент равным 71. Если вы разделите 600 851 475 143 на 71, вы получите 8 462 696 833. Оба эти числа разделяют одни и те же основные факторы, кроме 71. Теперь вы можете искать наибольший коэффициент исходного числа, но с пространством поиска уменьшено на 2 порядка.

Также обратите внимание, что ваш код не будет работать, если само число является простым. Чтобы исправить это, инициализируйте свое максимальное число как

int largest_prime_factor = 1; 

, и если он все еще 1 в конце, верните номер сам.(Вы можете инициализировать number, но вы скоро увидите, почему я выбрал 1)

Так начните путем обработки 2 как частный случай:

long long remain = number; 
    while (remain % 2 == 0) { 
      remain /= 2; 
      largest_prime_factor = 2; 
    } 

А затем сделать это так же внутри цикла. Поскольку для простых чисел нам нужно только проверить свой квадратный корень, мы ограничим наш цикл двумя случаями, в зависимости от того, считаем ли мы, что число может быть простым.

1. Тем не менее простое: проверить до SQRT (число)
2. больше не простое: испытание, пока максимальный коэффициент не превышает то, что остается.

В конце концов, ваш измененный код может выглядеть следующим образом:

#include <stdio.h> 

int main() 
{ 
    long long int number=600851475143; 
    long long largest_prime_factor = 1,i,j,k; 
    long long remain = number; 

    while (remain % 2 == 0) { 
     remain /= 2; 
     largest_prime_factor = 2; 
     /* Uncomment to see the factors 
      printf("2 ");*/ 
    } 

    for (i=3; (largest_prime_factor == 1 && i*i <= number) || 
      (largest_prime_factor > 1&& i <= remain); i+=2){ 
     k=0; 
     j=3; 
     for (j=3; j*j<=i;j+=2){ 
      if (i%j==0){ 
       k++;   
       break; 
      }   
     } 
     if (k==0 && remain%i==0) { 
      largest_prime_factor=i; 
      while (remain % i == 0) { 
       /* Uncomment to see the factors 
       printf("%d ", i); */ 
       remain /= i; 
      }    
     } 
    } 
    printf("The largest prime factor of %Ld is: %Ld", 
      number, largest_prime_factor); 
    return 0; 
} 

заметить также, что другие переменные также должны быть типа (длинный длинный).

Узкое место будет проверять, является ли каждое число простым, и весь процесс будет по-прежнему медленным, если сами основные факторы являются большими. Но вы можете получить гораздо более быстрый средний случай. Для вашего примера этот алгоритм получает коэффициенты 71, 839, 1471 и 6857 менее чем за секунду.

Answer 5

Использование j * j < = i вместо j < = sqrt (i), в зависимости от величины чисел, которые я использовал, сделал код в 5-10 раз быстрее. ++ к; вместо k ++; также оказали небольшое влияние. Примерно на 0,5%. И я еще не проверил все. Спасибо всем за ценные вклады! Есть много вещей, чтобы думать и узнавать о них благодаря им!