프로젝트 오일러 질문 3 도움
-
03-07-2019 - |
문제
나는 프로젝트 Euler를 통해 일하려고 노력하고 있으며 문제 03의 장벽을 치고 있습니다. 더 작은 숫자에 맞는 알고리즘이 있지만 문제 3은 매우 많은 숫자를 사용합니다.
문제 03 :13195의 주요 요인은 5, 7, 13 및 29입니다. 숫자 600851475143의 가장 큰 주요 요인은 무엇입니까?
다음은 C#의 솔루션이 있으며 1 시간 가까이 있다고 생각합니다. 나는 실제로 이것을 직접 해결하고 싶기 때문에 답을 찾고 있지 않습니다. 주로 도움을 찾고 있습니다.
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();
}
해결책
우선, N / 2에서 검색을 시작하는 대신 n의 제곱근에서 시작하십시오. 당신은 요인의 절반을 얻을 수 있고 나머지 절반은 보완입니다.
예 :
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.
다른 팁
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;
이것은 충분히 빠르야합니다 ... 통지, Prime을 확인할 필요가 없습니다 ...
실제로이 경우 원시를 확인할 필요가 없으며 찾은 요인 만 제거하십시오. n == 2로 시작하고 위쪽으로 스캔하십시오. Evil-Big-Number % n == 0 일 때, 악의-수를 n으로 나누고 작은 이벤 햄버를 계속하십시오. n> = sqrt (big-evil-number)를 중지하십시오.
현대 기계에서 몇 초 이상 걸리지 않아야합니다.
질문이 요청하지만 가장 큰 주요 요인, 반드시 먼저 그것을 찾아야한다는 의미는 아닙니다 ...
당신이하고있는 점검량을 줄여야합니다 ... 테스트해야 할 숫자에 대해 생각해보십시오.
더 나은 접근 방식을 위해 Erathosthenes의 체 ... 올바른 방향을 가리 킵니다.
NICF의 답변을 받아 들인 이유는 다음과 같습니다.
Euler의 문제는 괜찮지 만 일반적인 경우에는 효율적인 솔루션을 만들지는 않습니다. 왜 요인에 대해 짝수를 시도 하시겠습니까?
- n이 짝수 인 경우 더 이상 없을 때까지 좌회전 (2로 나누기)을 이동하십시오. 하나라면 2가 가장 큰 주요 요인입니다.
- N이조차도 안되면 짝수를 테스트 할 필요가 없습니다.
- sqrt (n)에서 멈출 수 있다는 것은 사실입니다.
- 요인에 대한 프라임 만 테스트하면됩니다. K가 n을 나누는 지 테스트 한 다음 원시를 테스트하는 것이 더 빠를 수 있습니다.
- 요인을 찾으면 즉시 상한을 최적화 할 수 있습니다.
이것은 다음과 같은 코드로 이어질 것입니다.
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)
모든 요소 2와 3이 제거 된 경우 N을 6로 나눈 적이 없기 때문에 초강화 된 몇 가지 모듈로 테스트가 있습니다. 당신은 i에 대한 프라임 만 허용 할 수 있습니다.
예를 들어 21의 결과를 살펴 보겠습니다.
21은조차도 아니기 때문에 상한 SQRT (21) (~ 4.6)로 FOR 루프로 들어갑니다. 그런 다음 21을 3으로 나눌 수 있으므로 결과 = 3 및 n = 21/3 = 7입니다. 이제 우리는 SQRT (7)까지까지 테스트하면됩니다. 3보다 작기 때문에 우리는 for 루프로 끝납니다. 우리는 n의 최대 n과 결과, 즉 n = 7을 반환합니다.
내가 한 방식은 프라임을 찾는 것이 었습니다.p
), Eratosthenes의 체를 사용하여 2에서 시작합니다. 이 알고리즘은 괜찮은 빠른 기계에서 <2s에서 천만 미만의 모든 프라임을 찾을 수 있습니다.
당신이 찾은 모든 프라임에 대해, 테스트는 더 이상 정수 부서를 할 수 없을 때까지 테스트하는 숫자로 나눕니다. (예 : 점검 n % p == 0
그리고 사실이라면, 나누기.)
한 번 n = 1
, 당신은 끝났습니다. 마지막 값 n
성공적으로 분열 된 것은 당신의 대답입니다. 사이드 노트에서, 당신은 또한 모든 주요 요인을 찾았습니다. n
도중에.
추신 : 이전에 언급했듯이, 당신은 사이의 프라임 만 검색하면됩니다. 2 <= n <= sqrt(p)
. 이것은 Eratosthenes의 체를 우리의 목적을 위해 알고리즘을 매우 빠르고 쉽게 구현할 수있게합니다.
답을 찾으면 브라우저에 다음을 입력하십시오.)
http://www.wolframalpha.com/input/?i=factorinteger(600851475143)
Wofram Alpha는 당신의 친구입니다
Java에서 재귀 알고리즘을 사용하는 것은 1 초 미만으로 실행됩니다. 제거 할 수있는 "Brute-Forcing"이 포함되어 있으므로 알고리즘을 조금씩 생각해보십시오. 또한 중간 계산으로 솔루션 공간을 어떻게 줄일 수 있는지 살펴보십시오.
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;
}
C ++ 의이 솔루션은 인텔 쿼드 코어 i5 IMAC (3.1GHz)에서 3.7ms를 차지했습니다.
#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;
}
모든 프로젝트 Euler의 문제는 1 분 이내에 걸립니다. 파이썬에서 최적화되지 않은 재귀 구현조차도 1 초 미만 [0.09 초 (CPU 4.3GHz)].
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
이것을보고 싶을 수도 있습니다.X가 프라임인지 판단 할 수 있고 단순한 필사자 프로그래머를 혼동하지 않는 간단한 알고리즘이 있습니까?
그리고 나는 Lill Mud의 해결책을 좋아합니다.
"mathn.rb"필요
600851475143.prime_division.last.first를 넣습니다
나는 그것을 확인했다 여기
어쩌면 그것은 부정 행위로 간주 될 수 있지만 Haskell의 한 가지 가능성은 글을 쓰는 것입니다 (레코드를 위해 직접 줄을 썼고 EulerProject 스레드를 확인하지 않았습니다).
import Data.Numbers.Primes
last (primeFactors 600851475143)
사용해보십시오 Miller-Rabin 원시 테스트 숫자가 프라임을 테스트합니다. 그것은 상당히 속도를 높여야합니다.
또 다른 접근법은 모든 프라임을 최대 N/2까지 얻은 다음 모듈러스가 0인지 확인하는 것입니다. N 찾을수있다 여기.