처음 10000개의 소수에 대한 가장 효율적인 코드는 무엇입니까?
https://stackoverflow.com/questions/622
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
처음 10000개의 소수를 인쇄하고 싶습니다.누구든지 나에게 가장 효율적인 코드를 줄 수 있습니까?설명:
- n >10000에 대해 코드가 비효율적인지 여부는 중요하지 않습니다.
- 코드의 크기는 중요하지 않습니다.
- 어떤 방식으로든 값을 하드 코딩할 수는 없습니다.
해결책
앳킨의 체 아마도 당신이 찾고 있는 것일 것입니다. 상한 실행 시간은 O(N/log log N)입니다.
6의 배수보다 1이 많고 1이 작은 숫자만 실행하면 3보다 큰 모든 소수는 6의 배수에서 1 떨어져 있기 때문에 훨씬 더 빠를 수 있습니다.내 진술에 대한 리소스
다른 팁
나는 체를 추천한다. 에라토스테네스의 체 아니면 그 앳킨의 체.
체 또는 에라토스테네스는 아마도 소수 목록을 찾는 가장 직관적인 방법일 것입니다.기본적으로 당신은:
- 2부터 원하는 한도(1000)까지의 숫자 목록을 적어보세요.
- 지워지지 않은 첫 번째 숫자(첫 번째 반복의 경우 2)를 선택하고 목록에서 해당 숫자의 배수를 모두 지웁니다.
- 목록 끝에 도달할 때까지 2단계를 반복합니다.지워지지 않은 숫자는 모두 소수입니다.
분명히 이 알고리즘이 더 빠르게 작동하도록 하기 위해 수행할 수 있는 최적화가 꽤 많이 있지만 이것이 기본 아이디어입니다.
Atkin의 체도 비슷한 접근 방식을 사용하지만 불행히도 나는 그것에 대해 설명할 만큼 지식이 없습니다.하지만 내가 연결한 알고리즘이 고대 Pentium II-350에서 최대 1000000000까지의 모든 소수를 알아내는 데 8초가 걸린다는 것을 알고 있습니다.
에라토스테네스의 체 소스 코드: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/
Atkin 소스 코드의 체: http://cr.yp.to/primegen.html
이는 엄격히 하드코딩 제한에 위배되는 것은 아니지만 매우 가깝습니다.대신 이 목록을 프로그래밍 방식으로 다운로드하여 인쇄해 보는 것은 어떨까요?
게이트킬러, 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보다 큰 자연수이며, 합성수는 각 소수의 배수를 열거하여 찾을 수 있습니다.":
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..]
(하스켈에서 괄호는 그룹화에 사용되며, 함수 호출은 단지 병치만으로 의미됩니다. (:) 는 단점 목록 연산자 (.) 함수형 합성 연산자입니다: (f . g) x = (\y -> f (g y)) x = f (g x)).
@매트:로그(로그(10000))는 ~2입니다.
Wikipedia 기사에서 (인용하신) 앳킨의 체:
이 체는 최대 N을 사용하여 프라임을 계산합니다
O(N/log log N)n 만있는 작업1/2+o(1) 기억의 비트.그것은 사용하는 Eratosthenes의 체보다 조금 낫습니다.O(N)연산과 O(N1/2(로그 로그 N)/로그 N) 메모리 비트 (A.O.L.앳킨, D.J.번스타인, 2004).이러한 점근 적 계산 복잡성에는 휠 인수 화와 같은 간단한 최적화 및 계산을 더 작은 블록으로 분할하는 것이 포함됩니다.
점근적 계산 복잡성을 고려하면 O(N) (에라토스테네스의 경우) 및 O(N/log(log(N))) (Atkin의 경우) 우리는 (작은 경우) 말할 수 없습니다 N=10_000) 구현하면 어떤 알고리즘이 더 빨라질까요?
Achim Flammenkamp는 다음과 같이 썼습니다. 에라토스테네스의 체:
인용:
@num1
반드시 10^9의 경우 약 10^9 정도의 간격의 경우, 에라 토스 테네의 체는 돌이킬 수없는 이진 2 차 형태를 사용하는 앳킨스와 번스타인의 체에 의해 성능이 우수합니다.배경 정보와 W.의 단락 5에 대한 논문을 참조하십시오.골웨이 박사.명제.
그러므로 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+$/
이것은 다음으로 구성된 문자열에 대해 테스트합니다. 케이 “1"에스, 케이 ~이다 소수가 아니다 (즉.문자열이 하나로 구성되어 있는지 여부1" 또는 "1"로 표현될 수 있다. N-ary 제품).
나는 코드프로젝트 다음을 생성합니다:
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에 작성한 에라토스테네스의 체입니다.반환되어야 하는 소수의 개수를 식별하는 매개변수가 있습니다.
#
# 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
적응하고 따라가기 게이트킬러, 여기에 제가 사용한 최종 버전이 있습니다.
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과 같은 솔루션보다 빠르지 않을 것이라고 생각합니다. .
파이썬에서
import gmpy
p=1
for i in range(10000):
p=gmpy.next_prime(p)
print p
그만큼 BenGoldberg가 언급한 deque sieve 알고리즘 매우 우아할 뿐만 아니라 때때로 실제로 유용할 수 있기 때문에 자세히 살펴볼 가치가 있습니다(순전히 학술적인 연습인 Atkin의 체와는 달리).
deque sieve 알고리즘의 기본 아이디어는 현재 '활성' 소인수 각각에 대해 최소한 하나의 별도 배수를 포함할 수 있을 만큼만 큰 작은 슬라이딩 체를 사용하는 것입니다.그 제곱이 현재 움직이는 체로 표시되는 가장 낮은 수를 초과하지 않는 소수입니다.SoE와의 또 다른 차이점은 데크 체(deque sieve)가 실제 요소를 부울이 아닌 합성 슬롯에 저장한다는 것입니다.
알고리즘은 필요에 따라 시브(sieve) 창의 크기를 확장하여 시브(sieve)가 CPU의 L1 캐시 용량을 눈에 띄게 초과하기 시작할 때까지 넓은 범위에 걸쳐 상당히 균일한 성능을 제공합니다.완전히 맞는 마지막 소수는 25,237,523(1,579,791번째 소수)이며, 이는 알고리즘의 합리적인 작동 범위에 대한 대략적인 대략적인 수치를 제공합니다.
이 알고리즘은 매우 간단하고 강력하며 분할되지 않은 에라토스테네스의 체보다 훨씬 더 넓은 범위에서 균일한 성능을 제공합니다.후자는 체(sieve)가 캐시에 완전히 맞는 한 훨씬 더 빠릅니다.바이트 크기의 bool이 있는 확률 전용 체의 경우 최대 2^16입니다.그런 다음 성능은 점점 더 떨어지지만, 핸디캡에도 불구하고 항상 deque보다 훨씬 빠릅니다(적어도 C/C++, Pascal 또는 Java/C#과 같은 컴파일된 언어에서는).
다음은 C#의 deque sieve 알고리즘을 렌더링한 것입니다. 그 이유는 이 언어가 많은 결함에도 불구하고 매우 번거롭고 현학적인 C++보다 프로토타입 알고리즘 및 실험에 훨씬 더 실용적이라는 것을 알았기 때문입니다. (참고:무료로 사용하고 있어요 LINQPad 프로젝트, 메이크파일, 디렉토리 등을 설정하는 데 번거로움 없이 바로 시작할 수 있으며 Python 프롬프트와 동일한 수준의 상호작용성을 제공합니다.
C#에는 명시적인 deque 유형이 없지만 일반 List<int> 알고리즘을 시연하기에 충분히 잘 작동합니다.
메모:이 버전은 소수에 대해 데크를 사용하지 않습니다. 왜냐하면 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인 특별한 세그먼트화된 에라토스테네스의 체로 상상하는 것입니다. 소수가 세그먼트 끝을 넘어갈 때 정지하는 오버플로 영역이 동반됩니다.세그먼트의 단일 셀(a.k.a. sieve[0])은 오버플로 영역의 일부인 동안 오버플로되었기 때문에 우리가 도달했을 때 이미 체로 걸러졌습니다.
로 표현되는 숫자 sieve[0] 에서 개최됩니다 sieve_base, 하지만 sieve_front 또는 window_base 또한 Ben의 코드나 분할/창이 있는 체 구현과 유사점을 그릴 수 있는 좋은 이름이 될 것입니다.
만약에 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 현재 소수보다 작은 소수의 배수가 될 수 없습니다. 그렇지 않으면 합성수로 표시됩니다.나는 그 값이 현재 소수의 제곱보다 작기 때문에 현재 소수의 더 높은 배수가 될 수 없습니다.그러므로 그것은 새로운 소수임에 틀림없다.
이 알고리즘은 분명히 에라토스테네스의 체(Sieve of Eratosthenes)에서 영감을 얻었지만, 마찬가지로 매우 다릅니다.에라토스테네스의 체는 기본 작업의 단순성에서 탁월한 속도를 얻습니다.단일 인덱스 추가와 각 작업 단계마다 하나의 저장이 오랜 시간 동안 수행되는 전부입니다.
다음은 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++로 작성되어야 했는데, 왜냐하면 적절한 deque 유형을 기반으로 하길 원했기 때문입니다(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#에 매우 좋으며 ìt는 다음을 보여줍니다. List<int> 데크라고 악용해도 나태하지 않다.
간단한 시브(sieve) 코드는 이미 정상적인 작업 범위를 넘어서 작동하고 있음에도 불구하고 여전히 deque를 물 밖으로 날려버립니다(부수적인 캐시 스래싱으로 L1 캐시 크기가 50% 초과됨).여기서 가장 중요한 부분은 체로 쳐진 소수를 읽는 것이며 이는 캐시 문제에 의해 크게 영향을 받지 않습니다.어쨌든 이 기능은 요인의 요인을 선별하기 위해 설계되었습니다.3단계 시브 계층 구조에서는 레벨 0이며 일반적으로 몇 백 개의 요소 또는 적은 수의 수천 개만 반환해야 합니다.따라서 단순함.
분할된 체를 사용하고 체질된 소수를 추출하기 위한 코드를 최적화하면 성능이 10배 이상 향상될 수 있지만(mod 3 단계로 두 번 풀거나 mod 15로 한 번 풀림) 더 많은 성능을 짜낼 수 있습니다. 모든 트리밍이 포함된 Mod 16 또는 Mod 30 휠을 사용하여 코드를 작성합니다(예:모든 잔류물에 대해 완전히 풀림).내 대답에 그런 것이 설명되어 있습니다. 소수 위치 소수 찾기 유사한 문제가 논의된 코드 검토에 대해 알아보세요.하지만 일회성 작업에 대해 밀리초 미만의 시간을 향상시키는 것이 포인트를 찾기는 어렵습니다...
상황을 조금 더 자세히 설명하기 위해 최대 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++ 타이밍을 사용할 수 없습니다).
모든 작업에 많은 비용이 들고 인터프리터 오버헤드가 예측과 예측으로 인한 모든 차이를 축소시키는 Python과 같은 해석된 언어에서는 상황이 확실히 다르게 보일 수 있습니다.잘못 예측된 분기 또는 하위 주기 작업(이동, 추가) 대다중 주기 연산(곱셈, 어쩌면 나눗셈).이는 에라토스테네스의 체의 단순성 이점을 약화시킬 수밖에 없으며, 이는 데크 솔루션을 좀 더 매력적으로 만들 수 있습니다.
또한 이 주제에 대해 다른 응답자들이 보고한 시기 중 상당수는 아마도 다음 사항에 의해 결정될 것입니다. 출력 시간.그것은 완전히 다른 전쟁입니다. 내 주요 무기는 다음과 같은 간단한 클래스입니다.
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,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 실행된다 O(log log n) 몇 번, 어디서 n 변수와 같습니다 maybe_prime.그 이유는 의 조건식 때문입니다. while 각 소인수에 대해 한 번씩 true로 평가됩니다. maybe_prime.보다 "제수 기능" 위키피디아에서.
횟수를 곱하면 my_insert 라고 불리며, 이 작업이 수행되어야 함을 보여줍니다. O(n log log n) 나열할 시간 n 소수...이는 당연히 에라토스테네스의 체가 가지고 있는 시간 복잡도입니다.
그러나 이 코드는 ~이다 효율적이지, 그건 아니야 가장 효율적인...다음과 같은 소수 생성을 위한 전문 라이브러리를 사용하는 것이 좋습니다. 프라임시브.진정으로 효율적이고 잘 최적화된 솔루션은 Stackoverflow에 입력하려는 것보다 더 많은 코드를 필요로 합니다.
에라토스테네스의 체(Sieve of Eratosthenes)를 사용하면 "알려진 전체" 소수 알고리즘에 비해 계산 속도가 상당히 빠릅니다.
Wiki의 의사 코드를 사용하여(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);
}
}
}
방금 배우기 시작했기 때문에 Python을 사용하여 이것을 작성했는데 완벽하게 작동합니다.10,000번째 소수는 위에서 언급한 것과 같은 코드로 생성됩니다. http://primes.utm.edu/lists/small/10000.txt.확인하려면 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 개의 프라임을 찾는 코드는 다음과 같습니다.
약간의 설명.이 방법은 소수를 찾기 위해 2가지 기술을 사용합니다.
- 우선, 소수가 아닌 숫자는 소수의 배수로 구성된 합성이므로 이 코드는 테스트 숫자를 숫자 대신 더 작은 소수로 나누어 테스트합니다. 이렇게 하면 4자리 숫자의 경우 계산이 최소 10배 감소하고 4자리 숫자의 경우 계산이 훨씬 더 줄어듭니다. 더 큰 숫자
- 두 번째로 소수로 나누는 것 외에도 테스트할 숫자의 근과 작거나 같은 소수로만 나누기 때문에 계산이 크게 줄어듭니다. 숫자의 근보다 큰 숫자는 다음과 같은 상대 숫자를 갖기 때문에 작동합니다. 숫자의 근보다 작아야 하지만 이미 근보다 작은 모든 숫자를 테스트했으므로 테스트할 숫자의 근보다 큰 숫자에 신경 쓸 필요가 없습니다.
처음 10,000개의 소수에 대한 샘플 출력
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk
다음은 C 언어로 된 코드입니다. 처음 10,000 프라임을 인쇄하려면 1, 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로만 나눕니다.
지금까지 내가 알아낸 가장 효율적인 방법.
복잡한 알고리즘을 코딩하는 대신 첫 번째 100000 프라임 만 원하기 때문에 다음을 제안하겠습니다.
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();
}
}
}
