algorithm - 판별 - 엣킨 의 체




숫자의 가장 큰 소수 요소를 찾는 알고리즘 (18)

"James Wang"이 웹에서이 솔루션을 발견했습니다.

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;
}

숫자의 가장 큰 소수 요소를 계산하는 가장 좋은 방법은 무엇입니까?

가장 효율적인 것은 다음과 같을 것이라고 생각합니다.

  1. 깨끗하게 나누는 가장 작은 소수를 찾는다.
  2. 분할 결과가 소수인지 확인
  3. 그렇지 않다면 다음으로 가장 낮은 것을 찾으십시오.
  4. 2로 가십시오.

저는 작은 가정 인자를 계산하는 것이 더 쉽다고 가정합니다. 이게 맞나요? 어떤 다른 접근법을 조사해야합니까?

편집 : 이제 2 개 이상의 소수가 있다면 내 접근 방식은 쓸모 없다는 것을 깨달았습니다. 결과는 2 개의 다른 소수의 결과이므로 2 단계가 실패하므로 재귀 알고리즘이 필요합니다.

다시 편집 : 그리고 지금 나는 이것이 여전히 작동한다는 것을 깨달았습니다. 왜냐하면 마지막으로 발견 된 소수는 가장 높은 소수이기 때문에 2 단계의 비 프라임 결과를 더 테스트하면 더 작은 소수가됩니다.


@ Triptych 대답과 유사하지만 또한 다릅니다. 이 예에서는 목록 또는 사전이 사용되지 않습니다. 코드는 Ruby로 작성되었습니다.

def largest_prime_factor(number)
  i = 2
  while number > 1
    if number % i == 0
      number /= i;
      i -= 1
    end
    i += 1
  end
  return i
end

largest_prime_factor(600851475143)
# => 6857

C ++에서 재귀를 사용하여 숫자의 가장 큰 소수 요소를 계산합니다. 코드 작업은 아래에 설명되어 있습니다.

int getLargestPrime(int number) {
    int factor = number; // assumes that the largest prime factor is the number itself
    for (int i = 2; (i*i) <= number; i++) { // iterates to the square root of the number till it finds the first(smallest) factor
        if (number % i == 0) { // checks if the current number(i) is a factor
            factor = max(i, number / i); // stores the larger number among the factors
            break; // breaks the loop on when a factor is found
        }
    }
    if (factor == number) // base case of recursion
        return number;
    return getLargestPrime(factor); // recursively calls itself
}

Java의 경우 :

int 값의 경우 :

public static int[] primeFactors(int value) {
    int[] a = new int[31];
    int i = 0, j;
    int num = value;
    while (num % 2 == 0) {
        a[i++] = 2;
        num /= 2;
    }
    j = 3;
    while (j <= Math.sqrt(num) + 1) {
        if (num % j == 0) {
            a[i++] = j;
            num /= j;
        } else {
            j += 2;
        }
    }
    if (num > 1) {
        a[i++] = num;
    }
    int[] b = Arrays.copyOf(a, i);
    return b;
}

long 값의 경우 :

static long[] getFactors(long value) {
    long[] a = new long[63];
    int i = 0;
    long num = value;
    while (num % 2 == 0) {
        a[i++] = 2;
        num /= 2;
    }
    long j = 3;
    while (j <= Math.sqrt(num) + 1) {
        if (num % j == 0) {
            a[i++] = j;
            num /= j;
        } else {
            j += 2;
        }
    }
    if (num > 1) {
        a[i++] = num;
    }
    long[] b = Arrays.copyOf(a, i);
    return b;
}

가장 빠르지는 않지만 작동합니다!

    static bool IsPrime(long num)
    {
        long checkUpTo = (long)Math.Ceiling(Math.Sqrt(num));
        for (long i = 2; i <= checkUpTo; i++)
        {
            if (num % i == 0)
                return false;
        }
        return true;
    }

가장 큰 소수 요소를 빨리 계산하는 방법은 다음과 같습니다. 사실 수정 된 x 에는 비 소수 요소가 포함되지 않습니다. 이를 달성하기 위해 요소가 발견 되 자마자 x 를 나눕니다. 그런 다음 남은 유일한 것은 가장 큰 요소를 반환하는 것입니다. 그것은 이미 소수 일 것입니다.

코드 (하스켈) :

f max' x i | i > x = max'
           | x `rem` i == 0 = f i (x `div` i) i  -- Divide x by its factor
           | otherwise = f max' x (i + 1)  -- Check for the next possible factor

g x = f 2 x 2

나는 그것을 현재의 주요 요인으로 나누는 알고리즘을 계속 사용하고 있습니다.

내 해결책은 파이썬 3 :

def PrimeFactor(n):
    m = n
    while n%2==0:
        n = n//2
    if n == 1:         # check if only 2 is largest Prime Factor 
        return 2
    i = 3
    sqrt = int(m**(0.5))  # loop till square root of number
    last = 0              # to store last prime Factor i.e. Largest Prime Factor
    while i <= sqrt :
        while n%i == 0:
            n = n//i       # reduce the number by dividing it by it's Prime Factor
            last = i
        i+=2
    if n> last:            # the remaining number(n) is also Factor of number 
        return n
    else:
        return last
print(PrimeFactor(int(input()))) 

입력 : 10 출력 : 5

입력 : 600851475143 출력 : 6857


나는 이것이 빠른 해결책이 아니라는 것을 알고있다. 희망에 따라 느린 해결책을 쉽게 이해할 수 있도록 게시하십시오.

 public static long largestPrimeFactor(long n) {

        // largest composite factor must be smaller than sqrt
        long sqrt = (long)Math.ceil(Math.sqrt((double)n));

        long largest = -1;

        for(long i = 2; i <= sqrt; i++) {
            if(n % i == 0) {
                long test = largestPrimeFactor(n/i);
                if(test > largest) {
                    largest = test;
                }
            }
        }

        if(largest != -1) {
            return largest;
        }

        // number is prime
        return n;
    } 

다음 C ++ 알고리즘은 최선의 알고리즘은 아니지만 10 억 이하의 숫자와 매우 빠른 속도로 작동합니다

#include <iostream>
using namespace std;

// ------ is_prime ------
// Determines if the integer accepted is prime or not
bool is_prime(int n){
    int i,count=0;
    if(n==1 || n==2)
      return true;
    if(n%2==0)
      return false;
    for(i=1;i<=n;i++){
    if(n%i==0)
        count++;
    }
    if(count==2)
      return true;
    else
      return false;
 }
 // ------ nextPrime -------
 // Finds and returns the next prime number
 int nextPrime(int prime){
     bool a = false;
     while (a == false){
         prime++;
         if (is_prime(prime))
            a = true;
     }
  return prime;
 }
 // ----- M A I N ------
 int main(){

      int value = 13195;
      int prime = 2;
      bool done = false;

      while (done == false){
          if (value%prime == 0){
             value = value/prime;
             if (is_prime(value)){
                 done = true;
             }
          } else {
             prime = nextPrime(prime);
          }
      }
        cout << "Largest prime factor: " << value << endl;
 }

모든 수는 소수의 곱으로 표현 될 수 있습니다. 예 :

102 = 2 x 3 x 17
712 = 2 x 2 x 2 x 89

단순히 2에서 시작하여 결과가 숫자의 배수가 될 때까지 나누기 만하면됩니다.

712 / 2 = 356 .. 356 / 2 = 178 .. 178 / 2 = 89 .. 89 / 89 = 1

이 방법을 사용하면 실제로 소수를 계산할 필요가 없습니다. 이미 모든 소수로 가능한 한 많은 수를 요소 화했기 때문에 모두 소수입니다.

number = 712;
currNum = number;    // the value we'll actually be working with
for (currFactor in 2 .. number) {
    while (currNum % currFactor == 0) {
        // keep on dividing by this number until we can divide no more!
        currNum = currNum / currFactor     // reduce the currNum
    }
    if (currNum == 1) return currFactor;    // once it hits 1, we're done.
}

소수를 먼저 저장하는 목록 계산, 예 : 2 3 5 7 11 13 ...

당신이 소수를 초등화 할 때마다 삼부작 (Triptych)에 의한 구현을 사용하지만 자연수보다는 소수의이 목록을 반복합니다.


숫자에서 모든 소수 요소를 제거하여 파이썬 반복 접근법

def primef(n):
    if n <= 3:
        return n
    if n % 2 == 0:
        return primef(n/2)
    elif n % 3 ==0:
        return primef(n/3)
    else:
        for i in range(5, int((n)**0.5) + 1, 6):
            #print i
            if n % i == 0:
                return primef(n/i)
            if n % (i + 2) == 0:
                return primef(n/(i+2))
    return n

여기 내가 아는 최고의 알고리즘 (파이썬에서)

def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1

    return factors


pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list

위의 방법은 최악의 경우 (입력이 소수 일 때 O(n) 에서 실행됩니다.

편집하다:
다음은 주석에 제안 된대로 O(sqrt(n)) 버전입니다. 여기에 코드가 있습니다.

def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1
        if d*d > n:
            if n > 1: factors.append(n)
            break
    return factors


pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list

이것은 항상 더 빠르지는 않지만 낙관적 인 것은 당신이 큰 소수를 발견한다는 것입니다.

  1. N 은 당신의 번호입니다.
  2. 그것이 소수라면 return(N)
  3. Sqrt(N) 까지 소수를 계산하십시오.
  4. 소수를 따라 내림차순으로 (가장 큰 것부터)
    • N is divisible by Prime 있다면 Return(Prime)

편집 : 3 단계에서 에라 토 스테 네스시 체 또는 앳킨스시 체를 사용할 수 있지만, 체 자체만으로는 가장 중요한 요소가되지 않습니다. (내가 SQLMenace의 공식 답변을 공식 답변으로 선택하지 않는 이유는 ...)


주어진 알고리즘의 2 단계가 그다지 효율적이지는 않습니다. 당신은 그것이 소수임을 합리적으로 기대하지 않습니다.

또한, 에라 토 스테 네스 체를 시사하는 이전의 대답은 전혀 잘못된 것입니다. 방금 123456789를 고려하는 두 가지 프로그램을 작성했습니다. 하나는 시브 (Sieve)를 기반으로했으며, 하나는 다음을 기반으로했습니다.

1)  Test = 2 
2)  Current = Number to test 
3)  If Current Mod Test = 0 then  
3a)     Current = Current Div Test 
3b)     Largest = Test
3c)     Goto 3. 
4)  Inc(Test) 
5)  If Current < Test goto 4
6)  Return Largest

이 버전은 Sieve보다 90 배 빠릅니다.

문제는 현대 프로세서에서 연산 유형이 연산 수보다 훨씬 적다는 것입니다. 위의 알고리즘이 캐시에서 실행될 수 있다는 것은 말할 것도없고, 시브 (Sieve)는 수행 할 수 없습니다. 시브 (Sieve)는 모든 복합 숫자를 알아내는 많은 작업을 사용합니다.

또한, 구분되는 요소를 구분하는 것은 테스트해야하는 공간을 줄여줍니다.


체를 사용한 프라임 팩터 :

#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;
}

#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();
 }

#python implementation
import math
n = 600851475143
i = 2
factors=set([])
while i<math.sqrt(n):
   while n%i==0:
       n=n/i
       factors.add(i)
   i+=1
factors.add(n)
largest=max(factors)
print factors
print largest




prime-factoring