300 000 000 000의 주요 요인?

Question

3 천억 이상의 주요 요인을 찾아야합니다. 나는 그것들의 목록에 추가하는 함수가 있습니다 ... 매우 느리게! 그것은 지금 약 1 시간 동안 달리고 있었고 나는 여전히 갈 수있는 상당한 거리가 있다고 생각합니다. 내가 완전히 잘못하고 있습니까? 아니면 이것이 기대됩니까?

편집 : Im 숫자 600851475143의 가장 큰 주요 요인을 찾으려고합니다.

편집 : 결과 :

{
    List<Int64> ListOfPrimeFactors = new List<Int64>();
    Int64 Number = 600851475143;
    Int64 DividingNumber = 2;

    while (DividingNumber < Number / DividingNumber)
    {
        if (Number % DividingNumber == 0)
        {
            ListOfPrimeFactors.Add(DividingNumber);
            Number = Number/DividingNumber;
        }
        else
            DividingNumber++;
        }
        ListOfPrimeFactors.Add(Number);
        listBox1.DataSource = ListOfPrimeFactors;
    }
}

Answer 1

당신은 당신이 그들을 찾을 때 각 요인별로 당신이 고려하는 숫자를 나누는 것을 기억하고 있습니까?

예를 들어, 2가 요인이라는 것을 알 수 있습니다. 요소 목록에 추가 할 수 있지만 해당 값으로 고려하려는 숫자를 나눕니다.

이제 당신은 1,500 억의 요인 만 찾고 있습니다. 주위에 매번 당신이 방금 찾은 요소에서 시작해야합니다. 따라서 2가 요인이라면 다시 테스트하십시오. 다음 요소가 3이면 2에서 다시 테스트가 없습니다.

등등...

Answer 2

중단기 힘을 사용하면 주요 요인을 찾는 것이 어렵습니다.이 기술은 사용하는 기술처럼 들립니다.

다음은 다소 속도를 높이기위한 몇 가지 팁입니다.

• 높지 않고 낮게 시작하십시오
• 프라임인지 확인하기 위해 각 잠재적 요소를 테스트하는 것을 방해하지 마십시오. 테스트가 소수 (1,3,7 또는 9로 끝나는 홀수).
• 짝수를 테스트하는 것을 귀찮게하지 마십시오 (모두 2로 나눌 수 있음) 또는 5로 끝나는 확률 (모두 5로 나눌 수 있음). 물론, 실제로 2와 5를 건너 뛰지 마십시오!
• 주요 요인을 찾으면이를 나누어야합니다. 대규모 원본 번호를 계속 사용하지 마십시오. 아래의 예를 참조하십시오.
• 요인을 찾으면 다시 테스트하여 여러 번 거기에 있는지 확인하십시오. 귀하의 번호는 2x2x3x7x7x7x31 이상일 수 있습니다.
• 도달하면 중지> = SQRT (남은 숫자)

편집 : 간단한 예 : 275의 요인을 찾고 있습니다.

1. 2로 분할 275를 테스트합니다. 275/2 = int (275/2)? 아뇨. 실패했습니다.
2. 3으로의 분할 가능성을 테스트합니다. 실패.
3. 건너 뛰기 4!
4. 5까지의 분할 가능성을 테스트하십시오. 예! 275/5 = 55. 따라서 새로운 테스트 번호는 이제 55입니다.
5. 테스트 55 5에 의한 분할을 위해. 예! 55/5 = 11. 따라서 새로운 테스트 번호는 이제 11입니다.
6. 그러나 5> sqrt (11), 11은 프라임이므로 멈출 수 있습니다!

그래서 275 = 5 * 5 * 11

더 이해가 되나요?

Answer 3

큰 숫자를 고려하는 것은 어려운 문제입니다. 실제로 우리는 RSA를 안전하게 유지하기 위해 그것에 의존합니다. 그러나 Wikipedia 페이지 도움이 될 수있는 알고리즘에 대한 일부 포인터. 그러나 작은 숫자의 경우, 당신이 어딘가에있을 필요가 없다는 것을 계속해서 다시 복용하지 않는 한, 그것은 실제로 그렇게 오래 걸리지 않아야합니다.

Brute-Force 솔루션의 경우 몇 가지 미니 최적화를 수행 할 수 있습니다.

• 2를 특별히 점검 한 다음 홀수 만 확인하십시오.
• 숫자의 제곱근을 확인하면됩니다 (그때까지 요인이 없으면 숫자가 프라임입니다).
• 요인을 찾으면 원래 숫자를 사용하여 다음 요인을 찾지 말고 찾은 요인으로 나누고 새 숫자를 검색하십시오.
• 요인을 찾으면 가능한 한 여러 번 나누어주십시오. 그 후에는 해당 숫자 또는 더 작은 숫자를 다시 확인할 필요가 없습니다.
• 위의 모든 작업을 수행하면 작은 요인이 이미 제거되었으므로 찾은 각 새로운 요소가 프라임이됩니다.

Answer 4

다음은 XSLT 솔루션입니다!

이 XSLT 변환은 0.109 초가 걸립니다.

<xsl:stylesheet version="2.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:xs="http://www.w3.org/2001/XMLSchema"
 xmlns:saxon="http://saxon.sf.net/"
 xmlns:f="http://fxsl.sf.net/"
 exclude-result-prefixes="xs saxon f"
 >
 <xsl:import href="../f/func-Primes.xsl"/>

 <xsl:output method="text"/>


 <xsl:template name="initial" match="/*">
   <xsl:sequence select="f:maxPrimeFactor(600851475143)"/>
 </xsl:template>

 <xsl:function name="f:maxPrimeFactor" as="xs:integer">
   <xsl:param name="pNum" as="xs:integer"/>

   <xsl:sequence select=
    "if(f:isPrime($pNum))
       then $pNum
       else
         for $vEnd in xs:integer(floor(f:sqrt($pNum, 0.1E0))),
             $vDiv1 in (2 to $vEnd)[$pNum mod . = 0][1],
             $vDiv2 in $pNum idiv $vDiv1
           return 
             max((f:maxPrimeFactor($vDiv1),f:maxPrimeFactor($vDiv2)))
    "/>
 </xsl:function>
</xsl:stylesheet>

이 변환은 단지 0.109 초만에 올바른 결과 (최대 원수 600851475143)를 생성합니다.:

6857

변환은 f:sqrt() 그리고 f:isPrime() 정의되었습니다 FXSL 2.0 - 기능 프로그래밍을위한 라이브러리 xslt. FXSL 그 자체가 완전히 쓰여졌습니다 xslt.

f:isPrime() 용도 Fermat의 작은 정리 원시를 결정하는 것이 효율적입니다.

Answer 5

아무도 언급하지 않았을 것입니다. 아마도 명백해 보일 것입니다. 요인을 찾아 나눌 때마다 요인이 실패 할 때까지 계속 노력하십시오.

64에는 하나의 주요 요인 만 있습니다.

Answer 6

$ time factor 300000000000 > /dev/null

real        0m0.027s
user        0m0.000s
sys         0m0.001s

한 시간이 걸리면 뭔가 잘못하고 있습니다. 어딘가에 무한 루프가있을 수도 있습니다. 32 비트 INT를 사용하지 않도록하십시오.

Answer 7

제곱근이 중요한 이유를 이해하는 열쇠는 N의 각 요소를 고려하십시오. 아래에 N의 제곱근에는 해당 요인이 있습니다 ~ 위에 그것. 이것을 보려면 x가 n의 계수 인 경우 x/n = m이므로 x/m = n이라는 것을 의미합니다.

Answer 8

나는 그것이 전혀 오래 걸릴 것으로 기대하지 않을 것입니다. 그것은 특히 많은 수가 아닙니다.

코드 어려움을 일으키는 예제 번호를 알려 주시겠습니까?

Answer 9

다음은 답을 얻을 수있는 사이트입니다. FACTORIS- 온라인 요인화 서비스. 정말 큰 숫자를 수행 할 수 있지만 대수 표현을 고려할 수도 있습니다.

Answer 10

가장 빠른 알고리즘은 체 알고리즘이며, 구현 및 테스트가 복잡한 개별 수학의 비전 영역 (적어도 내 머리 위로)을 기반으로합니다.

인수를위한 가장 간단한 알고리즘은 아마도 (다른 사람들이 말했듯이) Eratosthenes의 체일 것입니다. 숫자를 고려하기 위해 이것을 사용하는 것에 대해 기억해야 할 것 N:

• 일반적인 아이디어 : 가능한 정수 요인의 순서를 확인하고 있습니다. x 후보자 번호를 균등하게 나누는 지 확인합니다 N (C/Java/JavaScript에서 확인하십시오 N % x == 0)이 경우 N은 프라임이 아닙니다.
• 당신은 단지 올라 가야합니다 sqrt(N), 그러나 실제로 계산하지는 않습니다 sqrt(N): 테스트 계수 X가 테스트를 통과하는 한 루프 x*x<N
• 이전 프라임을 저장할 메모리가있는 경우 테스트 요소로만 사용하십시오 (Prime P가 테스트에 실패한 경우 저장하지 마십시오. P*P > N_max 다시는 사용하지 않을 것입니다
• 가능한 요인에 대해 이전 프라임을 저장하지 않더라도 x 2와 모든 홀수를 확인하십시오. 그렇습니다. 합리적인 크기의 숫자는 더 오래 걸리지 만 그리 오래 걸리지는 않습니다. 그만큼 프라임 카운팅 기능 그리고 근사치는 어떤 숫자의 일부가 주요한지를 알려줄 수 있습니다. 이 분수는 감소합니다 매우 느리게. 2에 대해서도⁶⁴ = 약 1.8x10¹⁹, 43 숫자 중 대략 1 개는 프라임입니다 (= 21.5 홀수 중 하나는 1이 프라임입니다). 2 미만의 요인의 경우⁶⁴, 그 요인들 x 2 미만입니다³² 여기서 20 숫자 중 약 1 개는 프라임입니다 = 10 홀수 중 하나는 프라임입니다. 따라서 10 배나 많은 숫자를 테스트해야하지만 루프는 조금 더 빠르며 모든 프라임을 저장하는 데 엉망이 될 필요는 없습니다.

또한 조금 더 복잡하지만 여전히 이해할 수있는 더 오래되고 간단한 체 알고리즘이 있습니다. 보다 딕슨, 생크스 그리고 Fermat 's 요인화 알고리즘. 나는 이것들 중 하나에 대한 기사를 한 번 읽었습니다. 어느 기사를 기억할 수 없지만, 그것들은 모두 매우 간단하고 사각형의 차이의 대수적 특성을 사용합니다.

숫자 여부를 테스트하는 경우 N 프라임이고, 당신은 실제로 요소 자체에 관심이없고, 확률 적 원시 테스트. 밀러-라빈 가장 표준적인 것 같아요.

Answer 11

나는 단지 나를 빨기 때문에 이것에 시간을 보냈다. 나는 아직 여기에 코드를 붙여 넣지 않을 것이다. 대신 참조하십시오 이 요소 .py gist 당신이 궁금하다면.

이 질문을 읽기 전에 (여전히 그렇지 않음) 고려해야 할 것에 대해 아무것도 몰랐습니다. 그것은 단지 파이썬 구현 일뿐입니다 Bradc위의 답변.

내 MacBook에서는 질문 (600851475143)에 언급 된 숫자를 고려하는 데 0.002 초가 걸립니다.

이 작업을 수행하는 훨씬 빠른 방법이 분명히 있어야합니다. 내 프로그램은 6008514751431331의 요인을 계산하는 데 19 초가 걸립니다. 그러나 요인 서비스는 정시에 답을 뱉어냅니다.

Answer 12

특정 번호는 300425737571입니까? 그것은 131 * 151 * 673 * 22567로 사소하게 요소를 요약합니다. 나는 모든 소란이 무엇인지 모르겠습니다 ...

Answer 13

여러분을위한 Haskell의 선함이 있습니다. :)

primeFactors n = factor n primes
  where factor n (p:ps) | p*p > n = [n]
                        | n `mod` p /= 0 = factor n ps
                        | otherwise = p : factor (n `div` p) (p:ps)
        primes = 2 : filter ((==1) . length . primeFactors) [3,5..]

그것들을 찾는 데 약 0.5 초가 걸렸으므로 그것을 성공이라고 부를 것입니다.

Answer 14

당신은 사용할 수 있습니다 에라 토스 테네스의 체 프라임을 찾아서 당신의 번호가 당신이 찾은 사람들에 의해 나눌 수 있는지 확인하려면.

Answer 15

나머지 모드 (n) 만 확인하면 n이 prime <= sqrt (n)인데, 여기서 n은 당신이 고려하려는 숫자입니다. 정말 느린 컴퓨터 나 TI-85에서도 한 시간 이상이 걸리지 않아야합니다.

Answer 16

알고리즘은 Fubar 여야합니다. 이것은 Python의 1.6GHz 넷북에서 약 0.1 초만 걸립니다. 파이썬은 타오르는 속도로 알려져 있지 않습니다. 그러나 그것은 임의의 정밀 정수를 가지고 있습니다 ...

import math
import operator

def factor(n):
    """Given the number n, to factor yield a it's prime factors.
    factor(1) yields one result: 1. Negative n is not supported."""
    M = math.sqrt(n)  # no factors larger than M
    p = 2             # candidate factor to test
    while p <= M:     # keep looking until pointless
        d, m = divmod(n, p)
        if m == 0:
            yield p   # p is a prime factor
            n = d     # divide n accordingly
            M = math.sqrt(n)  # and adjust M
        else:
            p += 1    # p didn't pan out, try the next candidate
    yield n  # whatever's left in n is a prime factor

def test_factor(n):
    f = factor(n)
    n2 = reduce(operator.mul, f)
    assert n2 == n

def example():
    n = 600851475143
    f = list(factor(n))
    assert reduce(operator.mul, f) == n
    print n, "=", "*".join(str(p) for p in f)

example()

# output:
# 600851475143 = 71*839*1471*6857

(이 코드는 숫자 이론에 대해 골무를 채울만큼 충분히 모른다는 사실을 도전하는 것으로 보입니다.)

Answer 17

"5로 끝나지 않는 홀수를 테스트하는 홀수 만 테스트 한 것"에서 약간 확장/개선하기 위해 ...

3보다 큰 모든 프라임은 x의 정수 값에 대해 6의 배수 또는 1 개보다 1 또는 1보다 적습니다.

Answer 18

비교적 순진한 무차별 인력으로도 오래 걸리지 않아야합니다. 그 특정 숫자의 경우 약 1 초 안에 머리에 고려할 수 있습니다.

당신은 솔루션을 원하지 않는다고 말하지만 여기에 당신의 "미묘한"힌트가 있습니다. 숫자의 유일한 주요 요인은 가장 낮은 3 프라임입니다.

Answer 19

해당 크기의 세미 프라임 번호는 암호화에 사용되므로 정확히 사용하려는 것에 대해 궁금합니다.

그 외에도 현재 비교적 적은 시간에 많은 수의 주요 인수를 찾는 좋은 방법은 없습니다.