소수(또는 소수)는 두 개의 작은 자연수의 곱이 아닌 1보다 큰 자연수입니다.
소수 찾기 알고리즘은 성능에 상당한 영향을 미칩니다. 특히 넓은 범위의 소수를 찾을 때는 효율적인 알고리즘을 선택해야 합니다. 에라토스테네스의 체와 같은 효율적인 알고리즘을 사용하세요.
PrimeFinder.cs
public class PrimeFinder
{
public List<int> FindPrimes(int n)
{
// Numbers less than 1 are not prime numbers
if (n <= 1)
{
return new List<int>();
}
// Assume all numbers are prime numbers.
var isPrime = new bool[n + 1];
for (int i = 2; i <= n; i++)
{
isPrime[i] = true;
}
// exclude multiples of p from prime numbers
for (int p = 2; p * p <= n; p++)
{
if (isPrime[p])
{
for (int i = p * p; i <= n; i += p)
{
isPrime[i] = false;
}
}
}
// add only prime numbers to list
var primes = new List<int>();
for (int i = 2; i <= n; i++)
{
if (isPrime[i])
{
primes.Add(i);
}
}
return primes;
}
}
</int></int></int>Program.cs
using System.Diagnostics; // for Stopwatch
Console.WriteLine("Hello, Day4!");
Console.Write("Enter a positive integer: ");
if (int.TryParse(Console.ReadLine(), out int n) && n > 0)
{
var primeFinder = new PrimeFinder();
// single loop
var stopwatch = Stopwatch.StartNew();
var primes = primeFinder.FindPrimes(n);
stopwatch.Stop();
var timeTaken = stopwatch.Elapsed.TotalMilliseconds;
foreach (var prime in primes)
{
Console.Write($"{prime} ");
}
Console.WriteLine($"Prime numbers up to {n}:");
Console.WriteLine($"Single loop Time taken: {timeTaken} ms");
}
else
{
Console.WriteLine("Invalid input. Please enter a positive integer.");
}
The beauty of this code lies in:
- 에라토스테네스의 체 적용: 이 코드는 에라토스테네스의 체 알고리즘을 사용하여 소수를 효율적으로 찾습니다. 중복 계산을 방지하고 모든 소수를 신속하게 식별합니다.
- 배열의 효과적인 사용: isPrime 배열은 숫자가 소수인지 아닌지를 저장하는 데 사용됩니다. 이 접근 방식은 중복 계산을 최소화합니다.
- 간결한 루프: for 루프는 간결하고 가독성을 향상시킵니다. 코드는 소수를 식별하기 위해 숫자를 우아하게 반복합니다.