Projeto Euler Pergunta 3 Ajuda
-
03-07-2019 - |
Pergunta
Eu estou tentando trabalhar através do Projeto Euler e eu estou batendo uma barreira no problema 03. Eu tenho um algoritmo que funciona para números menores, mas o problema 3 usa uma muito, muito grande número.
Problema 03: Os fatores primos de 13195 são 5, 7, 13 e 29. Qual é o maior fator primordial do número 600851475143?
Aqui está a minha solução em C # e ele foi correndo para eu acho que perto de uma hora. Eu não estou procurando uma resposta, porque eu realmente quero resolver isso sozinho. Principalmente apenas à procura de alguma ajuda.
static void Main(string[] args) {
const long n = 600851475143;
//const long n = 13195;
long count, half, largestPrime = 0;
bool IsAPrime;
half = n / 2;
for (long i = half; i > 1 && largestPrime == 0; i--) {
if (n % i == 0) { // these are factors of n
count = 1;
IsAPrime = true;
while (++count < i && IsAPrime) {
if (i % count == 0) { // does a factor of n have a factor? (not prime)
IsAPrime = false;
}
}
if (IsAPrime) {
largestPrime = i;
}
}
}
Console.WriteLine("The largest prime factor is " + largestPrime.ToString() + ".");
Console.ReadLine();
}
Solução
Para começar, em vez de começar a sua busca em n / 2, inicie-o na raiz quadrada de n. Você terá metade dos factores, sendo a outra metade do seu complemento.
por exemplo:
n = 27
start at floor(sqrt(27)) = 5
is 5 a factor? no
is 4 a factor? no
is 3 a factor? yes. 27 / 3 = 9. 9 is also a factor.
is 2 a factor? no.
factors are 3 and 9.
Outras dicas
long n = 600851475143L; //not even, so 2 wont be a factor
int factor = 3;
while( n > 1)
{
if(n % factor == 0)
{
n/=factor;
}else
factor += 2; //skip even numbrs
}
print factor;
Isso deve ser suficiente rápida ... Aviso, não há necessidade de verificar se há privilegiada ...
Na verdade, para este caso não é necessário para verificar se há primality, basta remover os fatores que você encontrar. Comece com n == 2 e digitalizar para cima. Quando o mal-big-número% n == 0, dividir o mal-big-número por n e continuar com pequeno-mal-número. Parar quando n> = sqrt (big-mal-número).
não deve levar mais do que alguns segundos em qualquer máquina moderna.
Embora a questão pede a maior fator primordial, que não significa necessariamente que você tem que encontrar esse primeiro ...
Você precisa reduzir a quantidade de verificar que você está fazendo ... pensar sobre o que os números que você precisa para teste.
Para uma melhor abordagem ler sobre o Crivo de Erathosthenes ... ele deve ficar você apontou na direção certa.
Quanto à razão para a resposta de nicf aceita:
É OK para o problema em Euler, mas não faz isso uma solução eficiente no caso geral. Por que você tente mesmo números de fatores?
- Se n é par, desvio à esquerda (dividir por 2) até que não é mais. Se for um, em seguida, 2 é o maior primo fator.
- Se n não é mesmo, você não tem que teste números pares.
- É verdade que você pode parar em sqrt (n).
- Você só tem que primes de teste para fatores. Pode ser mais rápido para teste se divide k N e, em seguida, testá-lo para primality embora.
- Você pode otimizar o limite superior da a mosca quando você encontra um fator.
Isso levaria a algum código como este:
n = abs(number);
result = 1;
if (n mod 2 = 0) {
result = 2;
while (n mod 2 = 0) n /= 2;
}
for(i=3; i<sqrt(n); i+=2) {
if (n mod i = 0) {
result = i;
while (n mod i = 0) n /= i;
}
}
return max(n,result)
Existem alguns testes modulo que são superflous, como n nunca pode ser dividido por 6 se todos os fatores 2 e 3 foram removidos. Você só poderia permitir primos para i.
Apenas como exemplo, vamos olhar para o resultado de 21:
21 não é mesmo, então vamos para o loop com sqrt limite superior (21) (~ 4,6). Podemos então dividir por 21 3, por conseguinte, resultar = 3 e n = 21/3 = 7. Vamos agora só tem a testar até sqrt (7). que é menor, em seguida, 3, de modo que são feitas com o loop. Voltamos ao máximo de n e resultado, que é n = 7.
A maneira que eu fiz era para procurar números primos (p
), a partir de 2, utilizando o Crivo de Eratóstenes. Este algoritmo pode encontrar todos os números primos menores de 10 milhões em <2s em uma máquina decentemente rápido.
Para cada nobre encontrar, dividir testá-lo para o número que você está testando contra até que você não pode fazer inteiro divisão mais. (Ie. Verificar n % p == 0
e se for verdade, então dividir.)
Uma vez n = 1
, você está feito. O último valor de n
que com sucesso dividido é sua resposta. Em uma nota, você também encontrou todos os fatores primos de n
no caminho.
PS: Como foi observado antes, você só precisa procurar primos entre 2 <= n <= sqrt(p)
. Isso torna o Crivo de Eratóstenes um muito rápido e fácil de implementar algoritmo para nossos propósitos.
Uma vez que você encontrar a resposta, digite o seguinte no seu browser;)
http://www.wolframalpha.com/input/?i= FactorInteger (600851475143)
Wofram Alpha é seu amigo
Usando um algoritmo recursivo em Java é executado menos de um segundo ... acho que seu algoritmo por um pouco, uma vez que inclui alguns "forçando brute-" que pode ser eliminado. Também olhar como seu espaço de solução pode ser reduzido em cálculos intermédios.
Fácil peasy em C ++:
#include <iostream>
using namespace std;
int main()
{
unsigned long long int largefactor = 600851475143;
for(int i = 2;;)
{
if (largefactor <= i)
break;
if (largefactor % i == 0)
{
largefactor = largefactor / i;
}
else
i++;
}
cout << largefactor << endl;
cin.get();
return 0;
}
Esta solução em C ++ levou 3,7 ms na minha Intel Quad Core i5 iMac (3,1 GHz)
#include <iostream>
#include <cmath>
#include <ctime>
using std::sqrt; using std::cin;
using std::cout; using std::endl;
long lpf(long n)
{
long start = (sqrt(n) + 2 % 2);
if(start % 2 == 0) start++;
for(long i = start; i != 2; i -= 2)
{
if(n % i == 0) //then i is a factor of n
{
long j = 2L;
do {
++j;
}
while(i % j != 0 && j <= i);
if(j == i) //then i is a prime number
return i;
}
}
}
int main()
{
long n, ans;
cout << "Please enter your number: ";
cin >> n; //600851475143L
time_t start, end;
time(&start);
int i;
for(i = 0; i != 3000; ++i)
ans = lpf(n);
time(&end);
cout << "The largest prime factor of your number is: " << ans << endl;
cout << "Running time: " << 1000*difftime(end, start)/i << " ms." << endl;
return 0;
}
problemas do All Projeto Euler deve levar menos de um minuto; mesmo uma implementação recursiva unoptimized em Python leva menos de um segundo [0,09 segundos (4.3GHz CPU)].
from math import sqrt
def largest_primefactor(number):
for divisor in range(2, int(sqrt(number) + 1.5)): # divisor <= sqrt(n)
q, r = divmod(number, divisor)
if r == 0:
#assert(isprime(divisor))
# recursion depth == number of prime factors,
# e.g. 4 has two prime factors: {2,2}
return largest_primefactor(q)
return number # number is a prime itself
Você pode querer ver isto: Existe um algoritmo simples que pode determinar se X é primo, e não confundir um simples programador mortal?
e eu como solução de lama lill:
exigem
"mathn.rb" puts 600851475143.prime_division.last.first
Eu verifiquei aqui
Talvez ele é considerado trapaça, mas uma possibilidade em Haskell é escrever (para o registro eu escrevi as linhas de mim e não tenho verificado tópicos eulerproject);
import Data.Numbers.Primes
last (primeFactors 600851475143)
Tente utilizar o Miller-Rabin Primality Teste para teste para um número ser primo . Isso deve acelerar as coisas consideravelmente.
Outra abordagem é fazer com que todos os números primos até n / 2 e depois para verificar se o módulo é 0. Um algoritmo que eu uso para obter todos os números primos até n pode ser encontrada aqui .