C에서 큰 숫자의 모든 요소/C++

Question

내가 10^18의 순서입니다 숫자의 모든 요소를 ​​찾기 위해 노력하고 있어요 ...하지만 문제를 만드는 시간 제약이 있습니다. 내가 한 일은 에라 토 스테 네스 시브 (Sieve of Eratosthenes)를 사용하여 요소를 찾고 요소를 저장하는 것이지만 속도는 느립니다 .......

Answer 1

공간이 문제가되지 않는다면 최대 소수점 목록을 저장할 수 있습니다 10^9 (목록은 download에 대해 사용 가능)을 사용하여 최대 10^18까지의 숫자를 분해 할 수 있습니다. 인수 분해 알고리즘 (예 : pollard의 rho 또는 others)을 사용할 수도 있습니다.

Answer 2

난 정말이 정수 인수 분해에 위키 기사를 읽고 추천 할 것입니다 : http://en.wikipedia.org/wiki/Integer_factorization

일반 목적의 인수 분해 방법이 느리다. 그러나 일부 특수 목적 방법을 사용하려고 할 수 있습니다.

Answer 3

팩터 번호 N < = 10^18에 소수 p < = 10^9의리스트를 저장하는 문제는 임의의 특정 N에 대해 여전히 소수를 반복해야한다는 것입니다. < = sqrt N), N % p == 0인지 확인하십시오. 이것은 비즈니스를 수행하는 가장 빠른 방법이 아닙니다.

주문 번호가 10^18 인 숫자의 묶음을 고려하고 싶거나 모두를 숫자 N < = 10^18으로 계산하려면 원하는지 확실하지 않습니다. 첫 번째 경우는 고려해야 할 N의 수와 얼마나 빨리해야하는지에 따라 다릅니다. 그 이상 동작 10^18 (고려되는 각각의 번호에 대한 적어도 하나)을 수반하기 때문에 모든 < 번호 N = 10^18을 고려해 두 번째 경우는, 행할 수 없다. 컴퓨터가 초당 10^9 작업의 순서로 수행 할 수 있고 그 해에 10^7 초 정도의 시간이 걸린다는 것을 고려하면 오랫동안 고려할 것입니다. 방금^18 (10)의 순서에 번호 N의 무리를 고려하려면

, 다음이 작업을 수행하는 많은 방법이있다. "가장 좋은"방법은 특정 숫자의 속성에 따라 다릅니다. 작은 요소보다 정교한 알고리즘으로 이동하기 전에 시험 구분하여 제거 할 수 있기 때문에, 예를 들어,^18 (10) 주위의 임의의 정수 개의 소수 위해 10^(9)의 각각의 산물 정수보다 평균 인자 훨씬 쉽다. 이것은 프로그래밍 문제보다 더 많은 계산 이론 이론 문제입니다. 이것이 귀하의 질문 인 경우 Factoring section of mersenneforum.org으로 문의하는 것이 좋습니다. 그런 다음 바퀴를 재발견하지 않는 터무니없이 느린없는 신속하고 더러운 솔루션을 원하는 경우

. 예를 들어 GMP-ECM을 시도하거나 PARI/GP가 문제를 해결할 수 있는지 확인하십시오. 실제로