Алгоритм нахождения наибольшего простого множителя числа

Question

Каков наилучший подход к вычислению наибольшего простого множителя числа?

Я думаю, что наиболее эффективным будет следующее:

1. Найдите наименьшее простое число, которое делит чисто
2. Проверить, является ли результат деления простым
3. Если нет, найдите следующий самый низкий
4. Перейти к 2.

Я основываю это предположение на том, что легче вычислить малые простые факторы. Это правильно? Какие еще подходы я должен рассмотреть?

Редактировать: Теперь я понял, что мой подход бесполезен, если в игре более двух основных факторов, поскольку шаг 2 не выполняется, когда результат является продуктом двух других простых чисел, поэтому необходим рекурсивный алгоритм. *

Снова отредактируйте: и теперь я понял, что это все еще работает, потому что последнее найденное простое число должно быть наибольшим, поэтому любое дальнейшее тестирование не простого результата из шага 2 приведет к меньшему простому .

Answer 1

Вероятно, это не всегда быстрее, но более оптимистично в отношении того, что вы найдете большой простой делитель:

1. N ваш номер
2. Если это простое число, то return(N)
3. Рассчитать простые числа до Sqrt(N)
4. Пройдите через простые числа в порядке убывания (сначала по возрастанию)
   • Если N is divisible by Prime, то Return(Prime)

Редактировать: На шаге 3 вы можете использовать Сито Эратосфена или Сито Аткинса или все, что вам нравится, но само по себе сито не найдет вас самым большим главным фактором. (Вот почему я не выбрал бы пост SQLMenace в качестве официального ответа ...)

Answer 2

Нашел это решение в сети от Джеймса Вана

public static int getLargestPrime( int number) {

    if (number <= 1) return -1;

    for (int i = number - 1; i > 1; i--) {
        if (number % i == 0) {
            number = i;
        }
    }
    return number;
}

Answer 3

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

factor(long int n)
{
long int i,j;
while(n>=4)
 {
if(n%2==0) {  n=n/2;   i=2;   }

 else
 { i=3;
j=0;
  while(j==0)
  {
   if(n%i==0)
   {j=1;
   n=n/i;
   }
   i=i+2;
  }
 i-=2;
 }
 }
return i;
 }

 void main()
 { 
  clock_t start = clock();
  long int n,sp;
  clrscr();
  printf("enter value of n");
  scanf("%ld",&n);
  sp=factor(n);
  printf("largest prime factor is %ld",sp);

  printf("Time elapsed: %f\n", ((double)clock() - start) / CLOCKS_PER_SEC);
  getch();
 }

Answer 4

Здесь та же функция @ Триптих, что и генератор, которая также немного упрощена.

def primes(n):
    d = 2
    while (n > 1):
        while (n%d==0):
            yield d
            n /= d
        d += 1

Максимальное простое число может быть найдено с помощью:

n= 373764623
max(primes(n))

и список факторов, найденных с использованием:

list(primes(n))

Answer 5

Сначала вычислите список, хранящий простые числа, например, 2 3 5 7 11 13 ...

Каждый раз, когда вы начинаете факторизацию числа, используйте реализацию от Triptych, но повторяйте этот список простых чисел, а не натуральные числа.

Answer 6

Коэффициент простоты с использованием сита:

#include <bits/stdc++.h>
using namespace std;
#define N 10001  
typedef long long ll;
bool visit[N];
vector<int> prime;

void sieve()
{
            memset( visit , 0 , sizeof(visit));
            for( int i=2;i<N;i++ )
            {
                if( visit[i] == 0)
                {
                    prime.push_back(i);
                    for( int j=i*2; j<N; j=j+i )
                    {
                        visit[j] = 1;
                    }
                }
            }   
}
void sol(long long n, vector<int>&prime)
{
            ll ans = n;
            for(int i=0; i<prime.size() || prime[i]>n; i++)
            {
                while(n%prime[i]==0)
                {
                    n=n/prime[i];
                    ans = prime[i];
                }
            }
            ans = max(ans, n);
            cout<<ans<<endl;
}
int main() 
{
           ll tc, n;
           sieve();

           cin>>n;
           sol(n, prime);

           return 0;
}

Answer 7

Я думаю, что было бы хорошо хранить где-нибудь все возможные простые числа, меньшие n, и просто перебирать их, чтобы найти самый большой делитель. Вы можете получить простые числа из prime-numbers.org .

Конечно, я предполагаю, что ваш номер не слишком большой:)