X가 프라임인지 판단 할 수 있고 단순한 필사자 프로그래머를 혼동하지 않는 간단한 알고리즘이 있습니까?
https://stackoverflow.com/questions/188425
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 프로젝트 Euler를 통해 내 길을 다루려고 노력했으며 소수의 문제가 그 일부로 소수를 결정하도록 요구하는 것을 발견했습니다.
나는 x를 2, 3, 4, 5, ..., x의 제곱근으로 나눌 수 있다는 것을 알고 있으며 제곱근에 도착하면 숫자가 프라임이라고 가정 할 수 있습니다. 불행히도이 솔루션은 상당히 klunky처럼 보입니다.
숫자가 프라임인지 판단하는 방법에 대한 더 나은 알고리즘을 살펴 보았지만 빠르게 혼란스러워합니다.
X가 프라임인지 판단 할 수 있고 단순한 필사자 프로그래머를 혼동하지 않는 간단한 알고리즘이 있습니까?
고맙습니다!
해결책
첫 번째 알고리즘은 상당히 좋으며 Project Euler에 많이 사용되었습니다. 원하는 최대 숫자를 알고 있다면 Eratosthenes의 체를 연구 할 수도 있습니다.
Primes 목록을 유지하는 경우 첫 번째 알고를 개선하여 숫자의 제곱근까지 프라임으로 만 나눌 수도 있습니다.
이 두 알고리즘 (나누기 및 체)을 사용하면 문제를 해결할 수 있어야합니다.
편집하다: 댓글에 언급 된 이름으로 수정되었습니다
다른 팁
한계 미만의 모든 소수를 생성합니다 에라 토스 테네스의 체 (이 페이지에는 20 개의 프로그래밍 언어의 변형이 포함되어 있음)는 가장 오래되고 가장 간단한 솔루션입니다.
파이썬에서 :
def iprimes_upto(limit):
is_prime = [True] * limit
for n in range(2, limit):
if is_prime[n]:
yield n
for i in range(n*n, limit, n): # start at ``n`` squared
is_prime[i] = False
예시:
>>> list(iprimes_upto(15))
[2, 3, 5, 7, 11, 13]
Fermat의 원시 테스트가 이미 제안되었지만 컴퓨터 프로그램의 구조 및 해석, 그리고 그들은 또한 Miller-Rabin 테스트 (1.2.6 절, 문제 1.28 절 참조) 다른 대안으로. 나는 오일러 문제에 대한 성공과 함께 그것을 사용하고 있습니다.
다음은 Eratosthenes의 체가는 아니지만 구현하기가 매우 쉽습니다. 먼저 x를 2와 3으로 나누고 J = 1..sqrt (x)/6을 통해 루프를 나누고 나누려고합니다. 6*J-1 및 6*J+1. 이것은 2 또는 3으로 나눌 수있는 모든 숫자에 대해 자동으로 건너 뜁니다.
다음 사실을 명심하십시오 ( mathschallenge.net):
- 2를 제외한 모든 프라임은 이상합니다.
- 3보다 큰 모든 프라임은 6K -1 또는 6K + 1 형식으로 작성할 수 있습니다.
- 당신은 n의 제곱근을 지나서 확인할 필요가 없습니다.
다음은 비교적 작은 N에 사용하는 C ++ 기능입니다.
bool isPrime(unsigned long n)
{
if (n == 1) return false; // 1 is not prime
if (n < 4) return true; // 2 and 3 are both prime
if ((n % 2) == 0) return false; // exclude even numbers
if (n < 9) return true; //we have already excluded 4, 6, and 8.
if ((n % 3) == 0) return false; // exclude remaining multiples of 3
unsigned long r = floor( sqrt(n) );
unsigned long f = 5;
while (f <= r)
{
if ((n % f) == 0) return false;
if ((n % (f + 2)) == 0) return false;
f = f + 6;
}
return true; // (in all other cases)
}
당신은 아마 자신의 최적화를 생각할 수 있습니다.
추천합니다 Fermat의 원시 테스트. 그것은 확률 론적 테스트이지만 놀랍게도 종종 정확합니다. 그리고 체와 비교할 때 엄청나게 빠릅니다.
합리적으로 적은 숫자의 경우 최대 SQRT (X)의 X%N은 매우 빠르고 코딩하기 쉽습니다.
간단한 개선 :
테스트 2 및 홀수 숫자 만.
테스트 2, 3 및 6 + 또는 -1의 배수 (2 또는 3 이외의 모든 프라임은 6 +/- 1의 배수이므로 본질적으로 모든 짝수와 3 개의 배수를 건너 뜁니다.
소수 만 테스트합니다 (모든 프라임을 SQRT (x)까지 계산하거나 저장해야합니다)
체 메소드를 사용하여 임의의 임의의 한계까지 모든 프라임 목록을 빠르게 생성 할 수 있지만 메모리 집약적 인 경향이 있습니다. 6 트릭의 배수를 사용하여 메모리 사용량을 숫자 당 1/3로 줄일 수 있습니다.
나는 6+1의 배수와 6-1의 배수에 2 개의 비트 필드를 사용하는 간단한 프라임 클래스 (c#)를 썼다. 그런 다음 간단한 조회를한다. 그런 다음 2, 3, 배수 6 +/- 1의 배수로 돌아갑니다. 큰 체를 생성하는 데 지금까지 해결 한 대부분의 오일러 문제에 대해 프라임을 계산하는 것보다 실제로 더 많은 시간이 걸립니다. 키스 원칙이 다시 파업!
나는 체를 사용하여 더 작은 프라임을 사전 계산 한 다음 2, 3으로 테스트에 의존하는 주요 클래스를 썼고 체의 범위 외부의 것들에 대해 6 +/-1의 배수에 의존합니다.
Project Euler의 경우 프라임 목록을 갖는 것이 정말 필수적입니다. 각 문제에 사용하는 목록을 유지하는 것이 좋습니다.
나는 당신이 찾고있는 것이 에라 토스 테네스의 체.
당신의 오른쪽 스마일이 가장 느립니다. 당신은 그것을 다소 최적화 할 수 있습니다.
정사각형 뿌리 대신 모듈러스를 사용하십시오. 프라임을 추적하십시오. 6은 2와 3의 배수이고 4는 2의 배수이기 때문에 7을 2, 3 및 5 만 분할하면됩니다.
rslite가 언급했습니다 에산데노스 체. 상당히 직접적입니다. 나는 그것을 집으로 여러 언어로 가지고 있습니다. 나중에 해당 코드를 게시하려면 주석을 추가하십시오.
여기 내 C ++가 있습니다. 개선 할 공간이 충분하지만 동적 언어 버전에 비해 빠릅니다.
// Author: James J. Carman
// Project: Sieve of Eratosthenes
// Description: I take an array of 2 ... max values. Instead of removeing the non prime numbers,
// I mark them as 0, and ignoring them.
// More info: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
#include <iostream>
int main(void) {
// using unsigned short.
// maximum value is around 65000
const unsigned short max = 50000;
unsigned short x[max];
for(unsigned short i = 0; i < max; i++)
x[i] = i + 2;
for(unsigned short outer = 0; outer < max; outer++) {
if( x[outer] == 0)
continue;
unsigned short item = x[outer];
for(unsigned short multiplier = 2; (multiplier * item) < x[max - 1]; multiplier++) {
unsigned int searchvalue = item * multiplier;
unsigned int maxValue = max + 1;
for( unsigned short maxIndex = max - 1; maxIndex > 0; maxIndex--) {
if(x[maxIndex] != 0) {
maxValue = x[maxIndex];
break;
}
}
for(unsigned short searchindex = multiplier; searchindex < max; searchindex++) {
if( searchvalue > maxValue )
break;
if( x[searchindex] == searchvalue ) {
x[searchindex] = 0;
break;
}
}
}
}
for(unsigned short printindex = 0; printindex < max; printindex++) {
if(x[printindex] != 0)
std::cout << x[printindex] << "\t";
}
return 0;
}
나는 내가 가진 Perl과 Python 코드와 파이썬 코드를 버릴 것입니다. 그들은 스타일이 비슷하고 줄이 적습니다.
다음은 D (디지털 화성)의 간단한 원시 테스트입니다.
/**
* to compile:
* $ dmd -run prime_trial.d
* to optimize:
* $ dmd -O -inline -release prime_trial.d
*/
module prime_trial;
import std.conv : to;
import std.stdio : w = writeln;
/// Adapted from: http://www.devx.com/vb2themax/Tip/19051
bool
isprime(Integer)(in Integer number)
{
/* manually test 1, 2, 3 and multiples of 2 and 3 */
if (number == 2 || number == 3)
return true;
else if (number < 2 || number % 2 == 0 || number % 3 == 0)
return false;
/* we can now avoid to consider multiples
* of 2 and 3. This can be done really simply
* by starting at 5 and incrementing by 2 and 4
* alternatively, that is:
* 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ...
* we don't need to go higher than the square root of the number */
for (Integer divisor = 5, increment = 2; divisor*divisor <= number;
divisor += increment, increment = 6 - increment)
if (number % divisor == 0)
return false;
return true; // if we get here, the number is prime
}
/// print all prime numbers less then a given limit
void main(char[][] args)
{
const limit = (args.length == 2) ? to!(uint)(args[1]) : 100;
for (uint i = 0; i < limit; ++i)
if (isprime(i))
w(i);
}
나는 프로젝트 Euler 문제를 통해 일하고 있으며 실제로 복합 수의 가장 높은 주요 요인을 검색하는 #3 (ID) (600851475143)을 검색하는 #3 (ID)을 완료했습니다.
나는 Primes (이미 언급 된 체 기술)와 Wikipedia의 정수 인수에 대한 모든 정보를 살펴보고 내가 결정한 Brute Force Trial Division 알고리즘을 생각해 냈습니다.
루비를 배우기 위해 오일러 문제를 수행 할 때 나는 알고리즘을 코딩하는 것을보고 있었고 주요 클래스 그리고 prime_division을 가진 정수 클래스 방법. 얼마나 멋진 지. 이 루비 스 니펫의 문제에 대한 정답을 얻을 수있었습니다.
require "mathn.rb"
puts 600851475143.prime_division.last.first
이 스 니펫은 콘솔에 대한 정답을 출력합니다. 물론 나는이 작은 아름다움을 우연히 발견하기 전에 많은 독서와 학습을하게되었다.
나는이 파이썬 코드를 좋아한다.
def primes(limit) :
limit += 1
x = range(limit)
for i in xrange(2,limit) :
if x[i] == i:
x[i] = 1
for j in xrange(i*i, limit, i) :
x[j] = i
return [j for j in xrange(2, limit) if x[j] == 1]
이것의 변형은 숫자의 요소를 생성하는 데 사용될 수 있습니다.
def factors(limit) :
limit += 1
x = range(limit)
for i in xrange(2,limit) :
if x[i] == i:
x[i] = 1
for j in xrange(i*i, limit, i) :
x[j] = i
result = []
y = limit-1
while x[y] != 1 :
divisor = x[y]
result.append(divisor)
y /= divisor
result.append(y)
return result
물론, 숫자 배치를 고려한다면 캐시를 다시 계산하지는 않을 것입니다. 나는 그것을 한 번하고, 그것을 조회 할 것입니다.
최적화되지는 않지만 매우 간단한 기능입니다.
function isprime(number){
if (number == 1)
return false;
var times = 0;
for (var i = 1; i <= number; i++){
if(number % i == 0){
times ++;
}
}
if (times > 2){
return false;
}
return true;
}
어쩌면 Java 에서이 구현이 도움이 될 수 있습니다.
public class SieveOfEratosthenes {
/**
* Calling this method with argument 7 will return: true true false false true false true false
* which must be interpreted as : 0 is NOT prime, 1 is NOT prime, 2 IS prime, 3 IS prime, 4 is NOT prime
* 5 is prime, 6 is NOT prime, 7 is prime.
* Caller may either revert the array for easier reading, count the number of primes or extract the prime values
* by looping.
* @param upTo Find prime numbers up to this value. Must be a positive integer.
* @return a boolean array where index represents the integer value and value at index returns
* if the number is NOT prime or not.
*/
public static boolean[] isIndexNotPrime(int upTo) {
if (upTo < 2) {
return new boolean[0];
}
// 0-index array, upper limit must be upTo + 1
final boolean[] isIndexNotPrime = new boolean[upTo + 1];
isIndexNotPrime[0] = true; // 0 is not a prime number.
isIndexNotPrime[1] = true; // 1 is not a prime number.
// Find all non primes starting from 2 by finding 2 * 2, 2 * 3, 2 * 4 until 2 * multiplier > isIndexNotPrime.len
// Find next by 3 * 3 (since 2 * 3 was found before), 3 * 4, 3 * 5 until 3 * multiplier > isIndexNotPrime.len
// Move to 4, since isIndexNotPrime[4] is already True (not prime) no need to loop..
// Move to 5, 5 * 5, (2 * 5 and 3 * 5 was already set to True..) until 5 * multiplier > isIndexNotPrime.len
// Repeat process until i * i > isIndexNotPrime.len.
// Assume we are looking up to 100. Break once you reach 11 since 11 * 11 == 121 and we are not interested in
// primes above 121..
for (int i = 2; i < isIndexNotPrime.length; i++) {
if (i * i >= isIndexNotPrime.length) {
break;
}
if (isIndexNotPrime[i]) {
continue;
}
int multiplier = i;
while (i * multiplier < isIndexNotPrime.length) {
isIndexNotPrime[i * multiplier] = true;
multiplier++;
}
}
return isIndexNotPrime;
}
public static void main(String[] args) {
final boolean[] indexNotPrime = SieveOfEratosthenes.isIndexNotPrime(7);
assert !indexNotPrime[2]; // Not (not prime)
assert !indexNotPrime[3]; // Not (not prime)
assert indexNotPrime[4]; // (not prime)
assert !indexNotPrime[5]; // Not (not prime)
assert indexNotPrime[6]; // (not prime)
assert !indexNotPrime[7]; // Not (not prime)
}
}
AKS 프라임 테스트 알고리즘 :
Input: Integer n > 1
if (n is has the form ab with b > 1) then output COMPOSITE
r := 2
while (r < n) {
if (gcd(n,r) is not 1) then output COMPOSITE
if (r is prime greater than 2) then {
let q be the largest factor of r-1
if (q > 4sqrt(r)log n) and (n(r-1)/q is not 1 (mod r)) then break
}
r := r+1
}
for a = 1 to 2sqrt(r)log n {
if ( (x-a)n is not (xn-a) (mod xr-1,n) ) then output COMPOSITE
}
output PRIME;
파이썬의 또 다른 방법은 다음과 같습니다.
import math
def main():
count = 1
while True:
isprime = True
for x in range(2, int(math.sqrt(count) + 1)):
if count % x == 0:
isprime = False
break
if isprime:
print count
count += 2
if __name__ == '__main__':
main()
