처음 10000 개의 소수에 대한 가장 효율적인 코드?
처음 10000 개의 소수를 인쇄하고 싶습니다. 누구든지 이것에 대해 가장 효율적인 코드를 줄 수 있습니까? 설명 :
- 코드가 n> 10000에 대해 비효율적인지 여부는 중요하지 않습니다.
- 코드의 크기는 중요하지 않습니다.
- 어떤 방식 으로든 값을 하드 코딩 할 수는 없습니다.
Atkin의 Sieve 는 아마도 당신이 찾고있는 것이고, 그것의 상한 실행 시간은 O (N / log log N)입니다.
6의 배수보다 1을 더 많이 실행하고 1을 더 적게 실행하는 경우, 3 이상의 모든 소수는 6의 배수에서 1만큼 떨어져 있기 때문에 더 빠를 수 있습니다. 내 진술에 대한 리소스
나는 에라토스테네스의 체 또는 앳킨 의 체를 추천한다 .
체 또는 에라토스테네스는 소수 목록을 찾는 가장 직관적 인 방법 일 것입니다. 기본적으로 :
- 2에서 원하는 한도까지 숫자 목록을 적으십시오. 1000이라고 가정합시다.
- 교차되지 않은 첫 번째 숫자 (첫 번째 반복의 경우 2)를 가져와 목록에서 해당 숫자의 모든 배수를 제거합니다.
- 목록 끝에 도달 할 때까지 2 단계를 반복하십시오. 교차되지 않은 모든 숫자는 소수입니다.
이 알고리즘이 더 빠르게 작동하도록하기 위해 수행 할 수있는 최적화가 꽤 많이 있지만 이것이 기본 아이디어입니다.
Atkin의 체는 비슷한 접근 방식을 사용하지만 불행히도 나는 당신에게 그것을 설명하기에 충분하지 않습니다. 하지만 내가 연결 한 알고리즘이 고대 펜티엄 II-350에서 1000000000까지의 모든 소수를 알아내는 데 8 초가 걸린다는 것을 알고 있습니다.
Sieve of Eratosthenes 소스 코드 : http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/
Sieve of Atkin 소스 코드 : http://cr.yp.to/primegen.html
이것은 엄격하게 하드 코딩 제한에 위배되는 것은 아니지만 매우 가깝습니다. 이 목록을 프로그래밍 방식으로 다운로드하여 인쇄하지 않는 이유는 무엇입니까?
http://primes.utm.edu/lists/small/10000.txt
GateKiller , 방법을 추가하는 방법에 대한 break것과 if에 foreach루프? 6이 2로 나눌 수 있다면 3과 5로 확인할 필요가 없기 때문에 많은 속도를 낼 것입니다 . (내가 충분한 평판을 얻었 으면 어쨌든 당신의 솔루션을 투표 할 것입니다 :-) ...)
ArrayList primeNumbers = new ArrayList();
for(int i = 2; primeNumbers.Count < 10000; i++) {
bool divisible = false;
foreach(int number in primeNumbers) {
if(i % number == 0) {
divisible = true;
break;
}
}
if(divisible == false) {
primeNumbers.Add(i);
Console.Write(i + " ");
}
}
하스켈에서 우리는 에라토스테네스 체의 수학적 정의를 거의 한마디로 쓸 수 있습니다. " 소수는 합성 수가없는 1 이상의 자연수입니다. 여기서 합성물은 각 소수의 배수를 열거하여 발견됩니다 ":
import Data.List.Ordered (minus, union)
primes = 2 : minus [3..] (foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r)
[] primes)
primes !! 10000 거의 즉각적입니다.
참조 :
위의 코드는 배당률에 대해서만 작업하도록 쉽게 조정됩니다 primes = 2 : 3 : minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)). 시간 복잡도는 트리와 같은 구조로 접음으로써 훨씬 개선되고 ( 최적 의 로그 계수 에 불과 ), 공간 복잡도는 다단계 프라임 생산에 의해 크게 향상 됩니다 .
primes = 2 : _Y ( (3:) . sieve 5 . _U . map (\p -> [p*p, p*p+2*p..]) )
where
_Y g = g (_Y g) -- non-sharing fixpoint combinator
_U ((x:xs):t) = x : (union xs . _U . pairs) t -- ~= nub.sort.concat
pairs (xs:ys:t) = union xs ys : pairs t
sieve k s@(x:xs) | k < x = k : sieve (k+2) s -- ~= [k,k+2..]\\s,
| otherwise = sieve (k+2) xs -- when s⊂[k,k+2..]
(하스켈에서 괄호 그룹화에 사용되는, 함수 호출은 단지 병렬 배치에 의해 표시되며, (:)A는 반대 목록의 운영자 및 (.)기능성 조성물 연산자이다 (f . g) x = (\y -> f (g y)) x = f (g x)).
@Matt : log (log (10000))은 ~ 2입니다.
위키피디아 기사 (당신이 인용 한)에서 Sieve of Atkin :
이 체는
O(N/log log N)N 1 / 2 + o (1) 비트의 메모리 만 사용하는 연산을 사용하여 최대 N 개의 소수를 계산 합니다. 이는O(N)연산과 O (N 1/2 (log log N) / log N) 비트의 메모리 를 사용하는 Eratosthenes의 체보다 약간 낫습니다 (AOL Atkin, DJ Bernstein, 2004) . 이러한 점근 적 계산 복잡성에는 휠 분해와 같은 간단한 최적화 및 계산을 더 작은 블록으로 분할하는 것이 포함됩니다.
O(N)(Eratosthenes의 경우) 및 O(N/log(log(N)))(Atkin의 경우) 점근 적 계산 복잡성이 주어지면 N=10_000구현 된 경우 어떤 알고리즘이 더 빠를 지 (작은 경우 ) 말할 수 없습니다 .
Achim Flammenkamp는 The Sieve of Eratosthenes에 다음 과 같이 썼습니다 .
인용 :
@ num1
약 10 ^ 9보다 큰 간격의 경우, 확실히> 10 ^ 10의 경우 에라토스테네스의 체는 환원 할 수없는 이진 2 차 형식을 사용하는 앳킨스 및 번스타인의 체보다 성능이 뛰어납니다. 배경 정보와 W. Galway의 Ph.D. 명제.
따라서 10_000에라토스테네스의 체는 앳킨의 체보다 빠를 수 있습니다.
OP에 답하기 위해 코드는 prime_sieve.c (에서 인용 num1)입니다.
GMP를 사용하면 다음과 같이 작성할 수 있습니다.
#include <stdio.h>
#include <gmp.h>
int main() {
mpz_t prime;
mpz_init(prime);
mpz_set_ui(prime, 1);
int i;
char* num = malloc(4000);
for(i=0; i<10000; i++) {
mpz_nextprime(prime, prime);
printf("%s, ", mpz_get_str(NULL,10,prime));
}
}
2.33GHz Macbook Pro에서 다음과 같이 실행됩니다.
time ./a.out > /dev/null
real 0m0.033s
user 0m0.029s
sys 0m0.003s
동일한 노트북에서 1,000,000 개의 소수 계산 :
time ./a.out > /dev/null
real 0m14.824s
user 0m14.606s
sys 0m0.086s
GMP는 이러한 종류의 작업에 고도로 최적화되어 있습니다. 직접 작성하여 알고리즘을 이해하고 싶지 않다면 C에서 libGMP를 사용하는 것이 좋습니다.
전혀 효율적이지는 않지만 정규식을 사용하여 소수를 테스트 할 수 있습니다.
/^1?$|^(11+?)\1+$/
이는 k " 1" 로 구성된 문자열에 대해 k 가 소수 가 아닌지 테스트합니다 (즉, 문자열이 하나의 " 1" 로 구성되어 있는지 아니면 n 항 곱 1으로 표현 될 수있는 " " 로 구성되어 있는지 여부 ).
CodeProject 에서 찾은 코드를 수정 하여 다음을 생성했습니다.
ArrayList primeNumbers = new ArrayList();
for(int i = 2; primeNumbers.Count < 10000; i++) {
bool divisible = false;
foreach(int number in primeNumbers) {
if(i % number == 0) {
divisible = true;
}
}
if(divisible == false) {
primeNumbers.Add(i);
Console.Write(i + " ");
}
}
내 ASP.NET 서버에서 이것을 테스트하는 데 약 1 분이 소요되었습니다.
며칠 전에 PowerShell에서 작성한 Eratosthenes의 Sieve가 있습니다. 반환되어야하는 소수의 수를 식별하기위한 매개 변수가 있습니다.
#
# generate a list of primes up to a specific target using a sieve of eratosthenes
#
function getPrimes { #sieve of eratosthenes, http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
param ($target,$count = 0)
$sieveBound = [math]::ceiling(( $target - 1 ) / 2) #not storing evens so count is lower than $target
$sieve = @($false) * $sieveBound
$crossLimit = [math]::ceiling(( [math]::sqrt($target) - 1 ) / 2)
for ($i = 1; $i -le $crossLimit; $i ++) {
if ($sieve[$i] -eq $false) {
$prime = 2 * $i + 1
write-debug "Found: $prime"
for ($x = 2 * $i * ( $i + 1 ); $x -lt $sieveBound; $x += 2 * $i + 1) {
$sieve[$x] = $true
}
}
}
$primes = @(2)
for ($i = 1; $i -le $sieveBound; $i ++) {
if($count -gt 0 -and $primes.length -ge $count) {
break;
}
if($sieve[$i] -eq $false) {
$prime = 2 * $i + 1
write-debug "Output: $prime"
$primes += $prime
}
}
return $primes
}
에라토스테네스의 체 는 단순함과 속도로 인해 갈 길입니다. C로 구현
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
int main(void)
{
unsigned int lim, i, j;
printf("Find primes upto: ");
scanf("%d", &lim);
lim += 1;
bool *primes = calloc(lim, sizeof(bool));
unsigned int sqrtlim = sqrt(lim);
for (i = 2; i <= sqrtlim; i++)
if (!primes[i])
for (j = i * i; j < lim; j += i)
primes[j] = true;
printf("\nListing prime numbers between 2 and %d:\n\n", lim - 1);
for (i = 2; i < lim; i++)
if (!primes[i])
printf("%d\n", i);
return 0;
}
프라임을 찾는 CPU 시간 (Pentium Dual Core E2140 1.6GHz, 단일 코어 사용)
~ 4 초 (lim = 100,000,000)
GateKiller 에서 적응하고 따라가는 것은 내가 사용한 최종 버전입니다.
public IEnumerable<long> PrimeNumbers(long number)
{
List<long> primes = new List<long>();
for (int i = 2; primes.Count < number; i++)
{
bool divisible = false;
foreach (int num in primes)
{
if (i % num == 0)
divisible = true;
if (num > Math.Sqrt(i))
break;
}
if (divisible == false)
primes.Add(i);
}
return primes;
}
기본적으로 동일하지만 "Sqrt 중단"제안을 추가하고 주변 변수 중 일부를 변경하여 더 적합하게 만들었습니다. (나는 오일러 작업을하고 있었고 10001 번째 프라임이 필요했습니다)
체가 잘못된 답인 것 같습니다. 체는 처음 N 개의 소수가 아닌 숫자 N 까지 소수를 제공합니다 . @Imran 또는 @Andrew Szeto를 실행하면 N까지 소수를 얻을 수 있습니다.
결과 세트의 특정 크기에 도달 할 때까지 점점 더 큰 숫자를 위해 체를 계속 시도하고 이미 얻은 숫자의 캐싱을 사용하면 체를 계속 사용할 수 있지만 @Pat과 같은 솔루션보다 빠르지 않을 것이라고 생각합니다. .
Python에서
import gmpy
p=1
for i in range(10000):
p=gmpy.next_prime(p)
print p
BenGoldberg 언급 양단 큐 체 알고리즘은 매우 우아한뿐만 아니라 때문에, 면밀한 관찰을받을 권리가 있지만, 또한 때때로 (순수하게 격식을 중요시하는 운동이다 Atkin의 체, 달리) 실제로 도움이 될 수 있기 때문이다.
deque sieve 알고리즘의 기본 아이디어는 현재 '활성'소인수 각각에 대해 하나 이상의 개별 배수를 포함 할 수있을 정도로만 크기가 작은 슬라이딩 체를 사용하는 것입니다. 즉, 제곱이 가장 낮은 수를 초과하지 않는 소수 현재 움직이는 체로 표시됩니다. SoE의 또 다른 차이점은 deque sieve가 실제 요소를 부울이 아닌 복합 슬롯에 저장한다는 것입니다.
알고리즘은 필요에 따라 시브 창의 크기를 확장하여 시브가 CPU의 L1 캐시 용량을 현저하게 초과하기 시작할 때까지 광범위한 범위에서 상당히 균일 한 성능을 제공합니다. 완전히 맞는 마지막 프라임은 25,237,523 (1,579,791st 프라임)이며, 알고리즘의 합리적인 작동 범위에 대한 대략적인 수치를 제공합니다.
이 알고리즘은 매우 간단하고 강력하며 분할되지 않은 에라토스테네스 체보다 훨씬 더 넓은 범위에서 성능을 발휘합니다. 후자는 시브가 캐시에 완전히 들어가는 한 훨씬 빠릅니다. 즉, 바이트 크기의 부울이있는 승산 전용 시브의 경우 최대 2 ^ 16입니다. 그런 다음 핸디캡에도 불구하고 (적어도 C / C ++, Pascal 또는 Java / C #과 같은 컴파일 된 언어에서) 항상 deque보다 훨씬 더 빠르지 만 성능은 점점 더 떨어집니다.
다음은 C #의 deque sieve 알고리즘의 렌더링입니다. 왜냐하면 그 언어는 많은 결함에도 불구하고 매우 번거롭고 현명한 C ++보다 프로토 타이핑 알고리즘과 실험에 훨씬 더 실용적이라는 것을 알기 때문입니다. (Sidenote : 저는 무료 LINQPad 를 사용하여 프로젝트, 메이크 파일, 디렉토리 또는 기타 설정에 대한 모든 지저분 함없이 바로 뛰어들 수 있으며 파이썬 프롬프트와 동일한 수준의 상호 작용을 제공합니다).
C #에는 명시 적 deque 유형이 없지만 일반 List<int>은 알고리즘을 보여주기에 충분합니다.
참고 :이 버전은 소수에 deque를 사용하지 않습니다. n 개의 소수에서 sqrt (n)을 꺼내는 것은 의미가 없기 때문입니다. 100 개의 프라임을 제거하고 9900을 남겨 두는 것이 무슨 소용이 있겠습니까? 적어도 이런 식으로 모든 소수가 깔끔한 벡터로 수집되어 추가 처리를 준비합니다.
static List<int> deque_sieve (int n = 10000)
{
Trace.Assert(n >= 3);
var primes = new List<int>() { 2, 3 };
var sieve = new List<int>() { 0, 0, 0 };
for (int sieve_base = 5, current_prime_index = 1, current_prime_squared = 9; ; )
{
int base_factor = sieve[0];
if (base_factor != 0)
{
// the sieve base has a non-trivial factor - put that factor back into circulation
mark_next_unmarked_multiple(sieve, base_factor);
}
else if (sieve_base < current_prime_squared) // no non-trivial factor -> found a non-composite
{
primes.Add(sieve_base);
if (primes.Count == n)
return primes;
}
else // sieve_base == current_prime_squared
{
// bring the current prime into circulation by injecting it into the sieve ...
mark_next_unmarked_multiple(sieve, primes[current_prime_index]);
// ... and elect a new current prime
current_prime_squared = square(primes[++current_prime_index]);
}
// slide the sieve one step forward
sieve.RemoveAt(0); sieve_base += 2;
}
}
다음은 두 가지 도우미 기능입니다.
static void mark_next_unmarked_multiple (List<int> sieve, int prime)
{
int i = prime, e = sieve.Count;
while (i < e && sieve[i] != 0)
i += prime;
for ( ; e <= i; ++e) // no List<>.Resize()...
sieve.Add(0);
sieve[i] = prime;
}
static int square (int n)
{
return n * n;
}
아마도 알고리즘을 이해하는 가장 쉬운 방법은 세그먼트 크기가 1 인 특별한 세그먼트 화 된 에라토스테네스 체로 상상하는 것입니다. 세그먼트의 단일 셀 (일명 sieve[0])은 이미 오버플로 영역의 일부인 동안 넘어 갔기 때문에 우리가 도달했을 때 이미 체질 된 것을 제외하고는 .
로 표현되는 수 sieve[0]에서 개최 sieve_base있지만, sieve_front나 window_base또한 벤의 코드 또는 분할 / 윈도우 자체의 구현에 평행선을 그릴 수 있도록 좋은 이름이 될 것입니다.
sieve[0]0이 아닌 값 이 포함 된 경우 해당 값은의 인수 sieve_base이므로 복합으로 인식 될 수 있습니다. 셀 0은 해당 계수의 배수이므로 다음 홉 (단순히 0에 해당 계수를 더한 값)을 계산하기 쉽습니다. 해당 셀이 이미 다른 요인에 의해 점유되고있는 경우, 다른 요인이 현재 주차되어 있지 않은 요인의 배수를 찾을 때까지 요인을 다시 추가합니다 (필요한 경우 체 확장). 이것은 또한 일반 세그먼트 체 에서처럼 한 세그먼트에서 다음 세그먼트로 다양한 프라임의 현재 작업 오프셋을 저장할 필요가 없음을 의미합니다. 에서 요소를 찾을 때마다 sieve[0]현재 작업 오프셋은 0입니다.
현재 프라임은 다음과 같은 방식으로 작용합니다. 프라임은 스트림에서 자체적으로 발생한 후에 만 전류가 될 수 있으며 (즉, 인자로 표시되지 않았기 때문에 프라임으로 감지 된 경우), sieve[0]정사각형에 도달 할 때까지 전류를 유지합니다 . 이 소수의 모든 낮은 배수는 일반 SoE에서와 같이 더 작은 소수의 활동으로 인해 제거되었을 것입니다. 그러나 정사각형의 유일한 요소는 소수 자체이고이 시점에서 아직 유통되지 않았기 때문에 더 작은 소수는 정사각형에서 벗어날 수 없습니다. 이는 경우에 알고리즘이 취한 조치를 설명합니다 sieve_base == current_prime_squared(를 의미 sieve[0] == 0합니다).
이제 사례 sieve[0] == 0 && sieve_base < current_prime_squared를 쉽게 설명 sieve_base할 수 있습니다 . 즉 , 현재 소수보다 작은 소수의 배수가 될 수 없으며 그렇지 않으면 복합으로 표시되었을 것입니다. 그 값이 현재 소수의 제곱보다 작기 때문에 나는 현재 소수의 배수가 될 수 없습니다. 그러므로 그것은 새로운 소수가되어야합니다.
이 알고리즘은 분명히 Eratosthenes의 Sieve에서 영감을 얻었지만 마찬가지로 분명히 매우 다릅니다. Eratosthenes의 Sieve는 기본 작업의 단순성에서 탁월한 속도를 얻습니다. 작업의 각 단계에 대해 하나의 단일 인덱스 추가와 하나의 저장소 만 있으면 오랜 시간 동안 수행 할 수 있습니다.
다음은 내가 일반적으로 ushort 범위, 즉 최대 2 ^ 16의 체질 인자 소수에 사용하는 단순하고 분할되지 않은 에라토스테네스 체입니다. 이 게시물을 위해 나는 대체하여 2 ^ 16 이상 일에 수정 한 int위해ushort
static List<int> small_odd_primes_up_to (int n)
{
var result = new List<int>();
if (n < 3)
return result;
int sqrt_n_halved = (int)(Math.Sqrt(n) - 1) >> 1, max_bit = (n - 1) >> 1;
var odd_composite = new bool[max_bit + 1];
for (int i = 3 >> 1; i <= sqrt_n_halved; ++i)
if (!odd_composite[i])
for (int p = (i << 1) + 1, j = p * p >> 1; j <= max_bit; j += p)
odd_composite[j] = true;
result.Add(3); // needs to be handled separately because of the mod 3 wheel
// read out the sieved primes
for (int i = 5 >> 1, d = 1; i <= max_bit; i += d, d ^= 3)
if (!odd_composite[i])
result.Add((i << 1) + 1);
return result;
}
처음 10000 개의 프라임을 체질 할 때 32KiByte의 일반적인 L1 캐시가 초과되지만 함수는 여전히 매우 빠릅니다 (C #에서도 1 밀리 초 단위).
이 코드를 deque sieve와 비교하면 deque sieve의 작동이 훨씬 더 복잡하다는 것을 쉽게 알 수 있으며, 항상 가능한 한 줄로 교차하는 길이를 최대한 짧게하기 때문에 오버 헤드를 효과적으로 분할 할 수 없습니다. (이미 교차 된 모든 배수를 건너 뛴 후 정확히 하나의 교차 교차).
참고 : C # 코드에서 사용하는 int대신 uint새로운 컴파일러가 이하의 코드를 생성하는 습관이 있기 때문에 uint내가 사용하는 위의 코드 ++ 버전 C에서 아마 부호있는 정수 대한 푸시 사람들에게 위해를, ... unsigned, 자연을 통해; 나는 그것이 가정 적절한 양단 큐 유형을 기반으로하고 싶었 기 때문에 벤치 마크는 C ++로해야했다 ( std::deque<unsigned>; 사용에서 성능에 이득이 없었다 unsigned short). 내 Haswell 노트북 (VC ++ 2015 / x64)의 번호는 다음과 같습니다.
deque vs simple: 1.802 ms vs 0.182 ms
deque vs simple: 1.836 ms vs 0.170 ms
deque vs simple: 1.729 ms vs 0.173 ms
참고 : C # 시간은 C ++ 타이밍의 거의 정확히 두 배입니다. 이는 C #에 매우 적합 List<int>하며 deque로 남용 되더라도 부끄럽지 않음을 보여 줍니다.
단순한 sieve 코드는 이미 정상적인 작업 범위를 넘어서 작동하고 있음에도 불구하고 여전히 물 밖으로 데크를 날려 버립니다 (L1 캐시 크기가 50 % 초과, 수반되는 캐시 스 래싱). 여기서 지배적 인 부분은 체질 된 소수를 읽는 것이며 이는 캐시 문제의 영향을 많이받지 않습니다. 어쨌든 함수는 요인의 요인 (예 : 3 단계 체 계층 구조의 수준 0)을 체질하기 위해 설계되었으며 일반적으로 몇 백 개의 요인 만 반환하거나 수천 개의 낮은 수를 반환해야합니다. 따라서 그 단순함.
세그먼트 화 된 체를 사용하고 체질 된 프라임을 추출하기위한 코드를 최적화함으로써 성능이 10 배 이상 향상 될 수 있습니다 (mod 3 단계 및 두 번 펼침 또는 mod 15 및 한 번 펼침). 모든 트리밍이있는 모드 16 또는 모드 30 휠을 사용하여 코드를 작성합니다 (예 : 모든 잔여 물에 대해 전체 풀기). 비슷한 문제가 논의 된 Code Review에서 소수 자리 잡은 소수 찾기에 대한 내 답변 에 설명되어 있습니다. 그러나 일회성 작업을 위해 밀리 초 미만의 시간을 개선하는 요점을보기는 어렵습니다 ...
대략적인 관점에서 살펴보기 위해 최대 100,000,000 개를 체질하는 C ++ 타이밍은 다음과 같습니다.
deque vs simple: 1895.521 ms vs 432.763 ms
deque vs simple: 1847.594 ms vs 429.766 ms
deque vs simple: 1859.462 ms vs 430.625 ms
대조적으로, 몇 가지 종소리와 휘파람이있는 C #의 분할 된 체는 95ms에서 동일한 작업을 수행합니다 (현재 C #에서만 코드 문제를 수행하기 때문에 C ++ 타이밍을 사용할 수 없음).
모든 작업에 막대한 비용이 들고 인터프리터 오버 헤드가 예측 된 대 잘못 예측 된 분기 또는 하위주기 연산 (이동, 추가) 대 다중주기 연산 (곱하기 , 그리고 아마도 나눗셈). 그것은 에라토스테네스의 체의 단순성 이점을 약화시킬 수 있으며, 이것은 데크 솔루션을 조금 더 매력적으로 만들 수 있습니다.
또한이 주제의 다른 응답자들이보고 한 많은 타이밍은 아마도 출력 시간에 의해 좌우 될 것입니다 . 그것은 완전히 다른 전쟁입니다. 여기서 제 주요 무기는 다음과 같은 단순한 클래스입니다.
class CCWriter
{
const int SPACE_RESERVE = 11; // UInt31 + '\n'
public static System.IO.Stream BaseStream;
static byte[] m_buffer = new byte[1 << 16]; // need 55k..60k for a maximum-size range
static int m_write_pos = 0;
public static long BytesWritten = 0; // for statistics
internal static ushort[] m_double_digit_lookup = create_double_digit_lookup();
internal static ushort[] create_double_digit_lookup ()
{
var lookup = new ushort[100];
for (int lo = 0; lo < 10; ++lo)
for (int hi = 0; hi < 10; ++hi)
lookup[hi * 10 + lo] = (ushort)(0x3030 + (hi << 8) + lo);
return lookup;
}
public static void Flush ()
{
if (BaseStream != null && m_write_pos > 0)
BaseStream.Write(m_buffer, 0, m_write_pos);
BytesWritten += m_write_pos;
m_write_pos = 0;
}
public static void WriteLine ()
{
if (m_buffer.Length - m_write_pos < 1)
Flush();
m_buffer[m_write_pos++] = (byte)'\n';
}
public static void WriteLinesSorted (int[] values, int count)
{
int digits = 1, max_value = 9;
for (int i = 0; i < count; ++i)
{
int x = values[i];
if (m_buffer.Length - m_write_pos < SPACE_RESERVE)
Flush();
while (x > max_value)
if (++digits < 10)
max_value = max_value * 10 + 9;
else
max_value = int.MaxValue;
int n = x, p = m_write_pos + digits, e = p + 1;
m_buffer[p] = (byte)'\n';
while (n >= 10)
{
int q = n / 100, w = m_double_digit_lookup[n - q * 100];
n = q;
m_buffer[--p] = (byte)w;
m_buffer[--p] = (byte)(w >> 8);
}
if (n != 0 || x == 0)
m_buffer[--p] = (byte)((byte)'0' + n);
m_write_pos = e;
}
}
}
10000 (정렬 된) 숫자를 쓰는 데 1ms 미만이 걸립니다. 최소한의 번거 로움과 제로 오버 헤드로 코딩 챌린지 제출에 텍스트 포함을위한 것이기 때문에 정적 클래스입니다.
일반적으로 집중 작업이 전체 배치에 대해 수행되면 훨씬 더 빠르다는 것을 알았습니다 . 즉, 특정 범위를 체로 뽑은 다음 모든 소수를 벡터 / 배열로 추출한 다음 전체 배열을 폭파 한 다음 다음 범위를 체질하는 등의 작업을 수행합니다. 모든 것을 함께 섞는 대신. 특정 작업에 초점을 맞춘 별도의 기능을 사용하면 혼합 및 일치가 더 쉬워지고 재사용이 가능하며 개발 / 테스트가 쉬워집니다.
다음은 업무용 랩톱에서 1 분 27 초 동안 10,000 만 미만의 소수를 모두 찾는 VB 2008 코드입니다. 짝수를 건너 뛰고 테스트 번호의 sqrt 미만인 소수만 찾습니다. 0에서 센티널 값까지 소수를 찾기 위해 설계되었습니다.
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles
Button1.Click
Dim TestNum As Integer
Dim X As Integer
Dim Z As Integer
Dim TM As Single
Dim TS As Single
Dim TMS As Single
Dim UnPrime As Boolean
Dim Sentinal As Integer
Button1.Text = "Thinking"
Button1.Refresh()
Sentinal = Val(SentinalTxt.Text)
UnPrime = True
Primes(0) = 2
Primes(1) = 3
Z = 1
TM = TimeOfDay.Minute
TS = TimeOfDay.Second
TMS = TimeOfDay.Millisecond
For TestNum = 5 To Sentinal Step 2
Do While Primes(X) <> 0 And UnPrime And Primes(X) ^ 2 <= TestNum
If Int(TestNum / Primes(X)) - (TestNum / Primes(X)) = 0 Then
UnPrime = False
End If
X = X + 1
Loop
If UnPrime = True Then
X = X + 1
Z = Z + 1
Primes(Z) = TestNum
End If
UnPrime = True
X = 0
Next
Button1.Text = "Finished with " & Z
TM = TimeOfDay.Minute - TM
TS = TimeOfDay.Second - TS
TMS = TimeOfDay.Millisecond - TMS
ShowTime.Text = TM & ":" & TS & ":" & TMS
End Sub
다음 Mathcad 코드는 3 분 이내에 처음 백만 개의 소수를 계산했습니다.
이것은 모든 숫자에 대해 부동 소수점 double을 사용하고 기본적으로 해석된다는 점을 명심하십시오. 구문이 명확하기를 바랍니다.
다음은 SoE 형식을 사용하는 C ++ 솔루션입니다.
#include <iostream>
#include <deque>
typedef std::deque<int> mydeque;
void my_insert( mydeque & factors, int factor ) {
int where = factor, count = factors.size();
while( where < count && factors[where] ) where += factor;
if( where >= count ) factors.resize( where + 1 );
factors[ where ] = factor;
}
int main() {
mydeque primes;
mydeque factors;
int a_prime = 3, a_square_prime = 9, maybe_prime = 3;
int cnt = 2;
factors.resize(3);
std::cout << "2 3 ";
while( cnt < 10000 ) {
int factor = factors.front();
maybe_prime += 2;
if( factor ) {
my_insert( factors, factor );
} else if( maybe_prime < a_square_prime ) {
std::cout << maybe_prime << " ";
primes.push_back( maybe_prime );
++cnt;
} else {
my_insert( factors, a_prime );
a_prime = primes.front();
primes.pop_front();
a_square_prime = a_prime * a_prime;
}
factors.pop_front();
}
std::cout << std::endl;
return 0;
}
이 버전의 Sieve는 소수를 무한정 계산할 수 있습니다.
또한 STL은주의 deque한다 O(1)수행 할 시간을 push_back, pop_front그리고 첨자하지만 랜덤 액세스.
resize동작에 걸리는 O(n)경우, 시간 n요소의 개수가 추가되고있다. 우리가이 함수를 사용하는 방법으로 인해 이것을 작은 상수로 취급 할 수 있습니다.
while루프 의 본문은 변수와 동일한 횟수 my_insert로 실행 됩니다. 이는 will의 조건식이의 각 소인수에 대해 한 번씩 true로 평가 되기 때문 입니다 . Wikipedia의 " Divisor 함수 "를 참조하십시오 .O(log log n)nmaybe_primewhilemaybe_prime
my_insert호출 횟수를 곱하면 소수 O(n log log n)를 나열하는 데 시간이 필요하다는 것을 알 수 있습니다 n. 이는 당연히 에라토스테네스의 체가 가져야하는 시간 복잡도입니다.
그러나이 코드 는 효율적 이기는하지만 가장 효율적인 것은 아닙니다 . 진정으로 효율적이고 최적화 된 솔루션은 누구나 Stackoverflow에 입력하려는 것보다 더 많은 코드를 필요로합니다.
Sieve of Eratosthenes를 사용하면 "알려진 전체"소수 알고리즘에 비해 계산이 훨씬 빠릅니다.
위키 ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ) 의 의사 코드를 사용하여 C #에 대한 솔루션을 가질 수 있습니다.
/// Get non-negative prime numbers until n using Sieve of Eratosthenes.
public int[] GetPrimes(int n) {
if (n <= 1) {
return new int[] { };
}
var mark = new bool[n];
for(var i = 2; i < n; i++) {
mark[i] = true;
}
for (var i = 2; i < Math.Sqrt(n); i++) {
if (mark[i]) {
for (var j = (i * i); j < n; j += i) {
mark[j] = false;
}
}
}
var primes = new List<int>();
for(var i = 3; i < n; i++) {
if (mark[i]) {
primes.Add(i);
}
}
return primes.ToArray();
}
GetPrimes (100000000)는 2 초와 330ms가 걸립니다.
참고 : 값은 하드웨어 사양에 따라 다를 수 있습니다.
나는 많은 소수를 계산하는 프로그램을 작성하는 데 시간을 할애하고 이것은 내가 처음 1.000.000.000 소수를 포함하는 텍스트 파일을 계산하는 데 사용되는 코드입니다. 독일어로되어 있지만 흥미로운 부분은 방법 calcPrimes()입니다. 소수는 Primzahlen이라는 배열에 저장됩니다. 계산이 64 비트 정수이므로 64 비트 CPU를 권장합니다.
import java.io.*;
class Primzahlengenerator {
long[] Primzahlen;
int LastUnknown = 2;
public static void main(String[] args) {
Primzahlengenerator Generator = new Primzahlengenerator();
switch(args.length) {
case 0: //Wenn keine Argumente übergeben worden:
Generator.printHelp(); //Hilfe ausgeben
return; //Durchfallen verhindern
case 1:
try {
Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
}
catch (NumberFormatException e) {
System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
break;//dutchfallen verhindern
case 2:
switch (args[1]) {
case "-l":
System.out.println("Sie müsen auch eine Datei angeben!"); //Hilfemitteilung ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
break;//durchfallen verhindern
case 3:
try {
Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
}
catch (NumberFormatException e) {
System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
Generator.printHelp(); //Generelle Hilfe ausgeben
return;
}
switch(args[1]) {
case "-l":
Generator.loadFromFile(args[2]);//Datei Namens des Inhalts von Argument 3 lesen, falls Argument 2 = "-l" ist
break;
default:
Generator.printHelp();
break;
}
break;
default:
Generator.printHelp();
return;
}
Generator.calcPrims();
}
void printHelp() {
System.out.println("Sie müssen als erstes Argument angeben, die wieviel ersten Primzahlen sie berechnen wollen."); //Anleitung wie man das Programm mit Argumenten füttern muss
System.out.println("Als zweites Argument können sie \"-l\" wählen, worauf die Datei, aus der die Primzahlen geladen werden sollen,");
System.out.println("folgen muss. Sie muss genauso aufgebaut sein, wie eine Datei Primzahlen.txt, die durch den Aufruf \"java Primzahlengenerator 1000 > Primzahlen.txt\" entsteht.");
}
void loadFromFile(String File) {
// System.out.println("Lese Datei namens: \"" + File + "\"");
try{
int x = 0;
BufferedReader in = new BufferedReader(new FileReader(File));
String line;
while((line = in.readLine()) != null) {
Primzahlen[x] = new Long(line).longValue();
x++;
}
LastUnknown = x;
} catch(FileNotFoundException ex) {
System.out.println("Die angegebene Datei existiert nicht. Bitte geben sie eine existierende Datei an.");
} catch(IOException ex) {
System.err.println(ex);
} catch(ArrayIndexOutOfBoundsException ex) {
System.out.println("Die Datei enthält mehr Primzahlen als der reservierte Speicherbereich aufnehmen kann. Bitte geben sie als erstes Argument eine größere Zahl an,");
System.out.println("damit alle in der Datei enthaltenen Primzahlen aufgenommen werden können.");
}
/* for(long prim : Primzahlen) {
System.out.println("" + prim);
} */
//Hier soll code stehen, der von der Datei mit angegebenem Namen ( Wie diese aussieht einfach durch angeben von folgendem in cmd rausfinden:
//java Primzahlengenerator 1000 > 1000Primzahlen.txt
//da kommt ne textdatei, die die primzahlen enthält. mit Long.decode(String ziffern).longValue();
//erhält man das was an der entsprechenden stelle in das array soll. die erste zeile soll in [0] , die zweite zeile in [1] und so weiter.
//falls im arry der platz aus geht(die exception kenn ich grad nich, aber mach mal:
//int[] foo = { 1, 2, 3};
//int bar = foo[4];
//dann kriegst ne exception, das ist die gleiche die man kriegt, wenn im arry der platzt aus geht.
}
void calcPrims() {
int PrimzahlNummer = LastUnknown;
// System.out.println("LAstUnknown ist: " + LastUnknown);
Primzahlen[0] = 2;
Primzahlen[1] = 3;
long AktuelleZahl = Primzahlen[PrimzahlNummer - 1];
boolean IstPrimzahl;
// System.out.println("2");
// System.out.println("3");
int Limit = Primzahlen.length;
while(PrimzahlNummer < Limit) {
IstPrimzahl = true;
double WurzelDerAktuellenZahl = java.lang.Math.sqrt(AktuelleZahl);
for(int i = 1;i < PrimzahlNummer;i++) {
if(AktuelleZahl % Primzahlen[i] == 0) {
IstPrimzahl = false;
break;
}
if(Primzahlen[i] > WurzelDerAktuellenZahl) break;
}
if(IstPrimzahl) {
Primzahlen[PrimzahlNummer] = AktuelleZahl;
PrimzahlNummer++;
// System.out.println("" + AktuelleZahl);
}
AktuelleZahl = AktuelleZahl + 2;
}
for(long prim : Primzahlen) {
System.out.println("" + prim);
}
}
}
나는 방금 배우기 시작한 파이썬을 사용하여 이것을 작성했으며 완벽하게 작동합니다. http://primes.utm.edu/lists/small/10000.txt에 언급 된 것과 동일하게이 코드에 의해 10,000 번째 소수가 생성됩니다 . n소수인지 아닌지 확인하려면 n에서 2까지 의 숫자로 나눕니다 sqrt(n). 이 숫자 범위 중 하나가 완벽하게 나뉘면 n소수가 아닙니다.
import math
print ("You want prime till which number??")
a = input()
a = int(a)
x = 0
x = int(x)
count = 1
print("2 is prime number")
for c in range(3,a+1):
b = math.sqrt(c)
b = int(b)
x = 0
for b in range(2,b+1):
e = c % b
e = int(e)
if (e == 0):
x = x+1
if (x == 0):
print("%d is prime number" % c)
count = count + 1
print("Total number of prime till %d is %d" % (a,count))
나는 약 1 년 동안 소수를 찾는 작업을 해왔습니다. 이것이 내가 가장 빠른 것으로 밝혀진 것입니다.
import static java.lang.Math.sqrt;
import java.io.PrintWriter;
import java.io.File;
public class finder {
public static void main(String[] args) {
primelist primes = new primelist();
primes.insert(3);
primes.insert(5);
File file = new File("C:/Users/Richard/Desktop/directory/file0024.txt");
file.getParentFile().mkdirs();
long time = System.nanoTime();
try{
PrintWriter printWriter = new PrintWriter ("file0024.txt");
int linenum = 0;
printWriter.print("2");
printWriter.print (" , ");
printWriter.print("3");
printWriter.print (" , ");
int up;
int down;
for(int i =1; i<357913941;i++){//
if(linenum%10000==0){
printWriter.println ("");
linenum++;
}
down = i*6-1;
if(primes.check(down)){
primes.insert(down);
//System.out.println(i*6-1);
printWriter.print ( down );
printWriter.print (" , ");
linenum++;
}
up = i*6+1;
if(primes.check(up)){
primes.insert(up);
//System.out.println(i*6+1);
printWriter.print ( up );
printWriter.print (" , ");
linenum++;
}
}
printWriter.println ("Time to execute");
printWriter.println (System.nanoTime()-time);
//System.out.println(primes.length);
printWriter.close ();
}catch(Exception e){}
}
}
class node{
node next;
int x;
public node (){
node next;
x = 3;
}
public node(int z) {
node next;
x = z;
}
}
class primelist{
node first;
int length =0;
node current;
public void insert(int x){
node y = new node(x);
if(current == null){
current = y;
first = y;
}else{
current.next = y;
current = y;
}
length++;
}
public boolean check(int x){
int p = (int)sqrt(x);
node y = first;
for(int i = 0;i<length;i++){
if(y.x>p){
return true;
}else if(x%y.x ==0){
return false;
}
y = y.next;
}
return true;
}
}
1902465190909 나노초는 2에서 시작하여 2147483629에 도달합니다.
다음은 랩톱에서 0.049655 초에 처음 10,000 개의 프라임, 6 초 이내에 처음 1,000,000 개의 프라임, 15 초 내에 처음 2,000,000 개를 찾는 코드입니다
. 이 방법은 두 가지 기술을 사용하여 소수를 찾습니다.
- 우선 소수가 아닌 숫자는 소수의 배수의 합성물이므로이 코드는 테스트 번호를 임의의 숫자 대신 작은 소수로 나누어 테스트합니다. 이렇게하면 4 자리 숫자에 대해 계산이 10 배 이상 감소합니다. 더 큰 숫자
- 두 번째로 소수로 나누는 것 외에도 테스트중인 숫자의 근보다 작거나 같은 소수로만 나눕니다. 계산을 더욱 줄여줍니다. 이는 수의 근보다 큰 숫자는 다음과 같은 대응 숫자를 갖기 때문입니다. 수의 근보다 작아야하지만 이미 근보다 작은 수를 모두 테스트 했으므로 테스트 할 수의 근보다 큰 수로 귀찮게 할 필요가 없습니다.
처음 10,000 개의 소수에 대한 샘플 출력
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk
다음은 C 언어로 된 코드입니다. 1을 입력 한 다음 10,000을 입력하여 처음 10,000 개의 소수를 인쇄합니다.
편집 : 여기에 수학 라이브러리가 포함되어 있음을 잊었습니다. Windows 또는 Visual Studio를 사용하는 경우 괜찮지 만 Linux에서는 -lm 인수를 사용하여 코드를 컴파일해야합니다. 그렇지 않으면 코드가 작동하지 않을 수 있습니다.
예 : gcc -Wall -o "% e ""% f "-lm
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <limits.h>
/* Finding prime numbers */
int main()
{
//pre-phase
char d,w;
int l,o;
printf(" 1. Find first n number of prime numbers or Find all prime numbers smaller than n ?\n"); // this question helps in setting the limits on m or n value i.e l or o
printf(" Enter 1 or 2 to get anwser of first or second question\n");
// decision making
do
{
printf(" -->");
scanf("%c",&d);
while ((w=getchar()) != '\n' && w != EOF);
if ( d == '1')
{
printf("\n 2. Enter the target no. of primes you will like to find from 3 to 2,000,000 range\n -->");
scanf("%10d",&l);
o=INT_MAX;
printf(" Here we go!\n\n");
break;
}
else if ( d == '2' )
{
printf("\n 2.Enter the limit under which to find prime numbers from 5 to 2,000,000 range\n -->");
scanf("%10d",&o);
l=o/log(o)*1.25;
printf(" Here we go!\n\n");
break;
}
else printf("\n Try again\n");
}while ( d != '1' || d != '2' );
clock_t start, end;
double cpu_time_used;
start = clock(); /* starting the clock for time keeping */
// main program starts here
int i,j,c,m,n; /* i ,j , c and m are all prime array 'p' variables and n is the number that is being tested */
int s,x;
int p[ l ]; /* p is the array for storing prime numbers and l sets the array size, l was initialized in pre-phase */
p[1]=2;
p[2]=3;
p[3]=5;
printf("%10dst:%10d\n%10dnd:%10d\n%10drd:%10d\n",1,p[1],2,p[2],3,p[3]); // first three prime are set
for ( i=4;i<=l;++i ) /* this loop sets all the prime numbers greater than 5 in the p array to 0 */
p[i]=0;
n=6; /* prime number testing begins with number 6 but this can lowered if you wish but you must remember to update other variables too */
s=sqrt(n); /* 's' does two things it stores the root value so that program does not have to calaculate it again and again and also it stores it in integer form instead of float*/
x=2; /* 'x' is the biggest prime number that is smaller or equal to root of the number 'n' being tested */
/* j ,x and c are related in this way, p[j] <= prime number x <= p[c] */
// the main loop begins here
for ( m=4,j=1,c=2; m<=l && n <= o;)
/* this condition checks if all the first 'l' numbers of primes are found or n does not exceed the set limit o */
{
// this will divide n by prime number in p[j] and tries to rule out non-primes
if ( n%p[j]==0 )
{
/* these steps execute if the number n is found to be non-prime */
++n; /* this increases n by 1 and therefore sets the next number 'n' to be tested */
s=sqrt(n); /* this calaulates and stores in 's' the new root of number 'n' */
if ( p[c] <= s && p[c] != x ) /* 'The Magic Setting' tests the next prime number candidate p[c] and if passed it updates the prime number x */
{
x=p[c];
++c;
}
j=1;
/* these steps sets the next number n to be tested and finds the next prime number x if possible for the new number 'n' and also resets j to 1 for the new cycle */
continue; /* and this restarts the loop for the new cycle */
}
// confirmation test for the prime number candidate n
else if ( n%p[j]!=0 && p[j]==x )
{
/* these steps execute if the number is found to be prime */
p[m]=n;
printf("%10dth:%10d\n",m,p[m]);
++n;
s = sqrt(n);
++m;
j=1;
/* these steps stores and prints the new prime number and moves the 'm' counter up and also sets the next number n to be tested and also resets j to 1 for the new cycle */
continue; /* and this restarts the loop */
/* the next number which will be a even and non-prime will trigger the magic setting in the next cycle and therfore we do not have to add another magic setting here*/
}
++j; /* increases p[j] to next prime number in the array for the next cycle testing of the number 'n' */
// if the cycle reaches this point that means the number 'n' was neither divisible by p[j] nor was it a prime number
// and therfore it will test the same number 'n' again in the next cycle with a bigger prime number
}
// the loops ends
printf(" All done !!\n");
end = clock();
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
printf(" Time taken : %lf sec\n",cpu_time_used);
}
내가 만든 코드는 다음과 같습니다.
enter code here
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT*/
unsigned long int n;
int prime(unsigned long int);
scanf("%ld",&n);
unsigned long int val;
for(unsigned long int i=0;i<n;i++)
{
int flag=0;
scanf("%ld",&val);
flag=prime(val);
if(flag==1)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
int prime(unsigned long int n)
{
if(n==2) return 1;
else if (n == 1||n%2==0) return 0;
for (unsigned long int i=3; i<=sqrt(n); i+=2)
if (n%i == 0)
return 0;
return 1;
}
Javascript에서 Array.prototype.find () 메서드 사용. 2214.486ms
function isPrime (number) {
function prime(element) {
let start = 2;
while (start <= Math.sqrt(element)) {
if (element % start++ < 1) {
return false;
}
}
return element > 1;
}
return [number].find(prime)
}
function logPrimes (n) {
let count = 0
let nth = n
let i = 0
while (count < nth) {
if (isPrime(i)) {
count++
console.log('i', i) //NOTE: If this line is ommited time to find 10,000th prime is 121.157ms
if (count === nth) {
console.log('while i', i)
console.log('count', count)
}
}
i++
}
}
console.time(logPrimes)
logPrimes(10000)
console.timeEnd(logPrimes) // 2214.486ms
몇 가지 팁을 드릴 수 있습니다. 구현해야합니다.
- 각 숫자에 대해 해당 숫자의 절반을 얻습니다. 예를 들어 21을 확인하는 경우 2-10 범위에서 나눈 나머지 만 얻습니다.
- 홀수이면 홀수로만 나누고 그 반대의 경우도 마찬가지입니다. 예를 들어 21의 경우 3, 5, 7, 9로만 나눕니다.
지금까지 가장 효율적인 방법입니다.
복잡한 알고리즘을 코딩하는 대신 처음 10000 소수만 원하므로 다음을 제안합니다.
boolean isPrime(int n){
//even but is prime
if(n==2)
return true;
//even numbers filtered already
if(n==0 || n==1 || n%2==0)
return false;
// loop for checking only odd factors
// i*i <= n (same as i<=sqrt(n), avoiding floating point calculations)
for(int i=3 ; i*i <=n ; i+=2){
// if any odd factor divides n then its not a prime!
if(n%i==0)
return false;
}
// its prime now
return true;
}
이제 필요에 따라 전화가 프라임입니다.
for(int i=1 ; i<=1000 ; i++){
if(isPrime(i)){
//do something
}
}
using System;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
int n, i = 3, j, c;
Console.WriteLine("Please enter your integer: ");
n = Convert.ToInt32(Console.ReadLine());
if (n >= 1)
{
Console.WriteLine("First " + n + " Prime Numbers are");
Console.WriteLine("2");
}
for(j=2;j<=n;)
{
for(c=2;c<=i-1;c++)
{
if(i%c==0)
break;
}
if(c==i)
{
Console.WriteLine(i);
j++;
}
i++;
}
Console.Read();
}
}
}
참조 URL : https://stackoverflow.com/questions/622/most-efficient-code-for-the-first-10000-prime-numbers
'UFO ET IT' 카테고리의 다른 글
| 선형 레이아웃을 수직 중앙에 정렬하는 방법은 무엇입니까? (0) | 2021.01.09 |
|---|---|
| unique_ptr :: release ()는 소멸자를 호출합니까? (0) | 2021.01.09 |
| Core Data Managed Object를 복제하거나 복사하려면 어떻게해야합니까? (0) | 2021.01.09 |
| SQL Server 2008은 특수 스키마 아래의 모든 테이블을 삭제합니다. (0) | 2021.01.09 |
| 장고 템플릿의 변수 빼기 (0) | 2021.01.09 |