소수를 찾는 프로그램
https://stackoverflow.com/questions/1510124
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
0과 긴 변수 사이의 소수를 찾고 싶지만 출력을 얻을 수 없습니다.
프로그램은
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication16
{
class Program
{
void prime_num(long num)
{
bool isPrime = true;
for (int i = 0; i <= num; i++)
{
for (int j = 2; j <= num; j++)
{
if (i != j && i % j == 0)
{
isPrime = false;
break;
}
}
if (isPrime)
{
Console.WriteLine ( "Prime:" + i );
}
isPrime = true;
}
}
static void Main(string[] args)
{
Program p = new Program();
p.prime_num (999999999999999L);
Console.ReadLine();
}
}
}
누구든지 나를 도와주고 프로그램에서 발생할 수 있는 오류가 무엇인지 찾아낼 수 있습니까?
해결책
다음을 사용하면 더 빠르게 이 작업을 수행할 수 있습니다. 거의 최적 다음과 같이 하나의 (긴) 줄로 시험 분할 체를 만듭니다.
Enumerable.Range(0, Math.Floor(2.52*Math.Sqrt(num)/Math.Log(num))).Aggregate(
Enumerable.Range(2, num-1).ToList(),
(result, index) => {
var bp = result[index]; var sqr = bp * bp;
result.RemoveAll(i => i >= sqr && i % bp == 0);
return result;
}
);
여기에 사용된 소수의 수에 대한 근사 공식은 다음과 같습니다. π(x) < 1.26 x / ln(x).우리는 다음보다 크지 않은 소수로만 테스트하면 됩니다. x = sqrt(num).
참고 에라토스테네스의 체 시험 분할보다 런타임 복잡성이 훨씬 더 높습니다(더 큰 경우 훨씬 더 빠르게 실행되어야 함). num 올바르게 구현된 경우 값).
다른 팁
이 시도:
void prime_num(long num)
{
// bool isPrime = true;
for (long i = 0; i <= num; i++)
{
bool isPrime = true; // Move initialization to here
for (long j = 2; j < i; j++) // you actually only need to check up to sqrt(i)
{
if (i % j == 0) // you don't need the first condition
{
isPrime = false;
break;
}
}
if (isPrime)
{
Console.WriteLine ( "Prime:" + i );
}
// isPrime = true;
}
}
숫자의 제곱근까지 홀수 디바이저를 확인하면됩니다. 다시 말해 내부 루프가 시작해야합니다.
for (int j = 3; j <= Math.Sqrt(i); j+=2) { ... }
또한 숫자가 주요한 것이 아니라는 것을 알게되면 기능에서 벗어날 수 있습니다. 더 이상 디바이저를 확인할 필요가 없습니다 (이미 그렇게하고 있습니다!).
NUM이 2보다 큰 경우에만 작동합니다.
SQRT 없음
실행 합계를 유지함으로써 SQRT를 완전히 피할 수 있습니다. 예를 들어:
int square_sum=1;
for (int j=3; square_sum<i; square_sum+=4*(j++-1)) {...}
숫자 1+ (3+5)+(7+9)의 합이 홀수 제곱 (1,9,25 등)을 제공하기 때문입니다. 따라서 j 의 제곱근을 나타냅니다 square_sum. 하는 한 square_sum 보다 적습니다 i 그 다음에 j 제곱근보다 작습니다.
사람들은이 작업을 효율적으로 수행하기 위해 두 개의 빌딩 블록을 언급했지만 아무도 실제로 조각을 모으지 않습니다. 그만큼 에라 토스 테네스의 체 좋은 출발이지만, 그로 인해 기억이 떨어질 것입니다. 긴 한계에 도달하기 전에 설정했습니다. 그렇다고해서 쓸모가 없다는 것을 의미하지는 않습니다. 루프를 할 때 실제로 관심이있는 것은 프라임 디바이저입니다. 따라서 체를 사용하여 프라임 디바이저의베이스를 만들고 루프에있는 것들을 사용하여 우선 순위를 테스트하는 것으로 시작할 수 있습니다.
그러나 루프를 쓰면 몇 가지 답변이 제안한대로 루프 조건에서 SQRT (i)를 실제로 원하지 않습니다. 당신과 나는 SQRT가 동일한 입력 매개 변수가 주어지면 항상 동일한 대답을 제공하는 "순수한"함수라는 것을 알고 있습니다. 불행히도, 컴파일러는 루프 조건에서 '<= math.sqrt (x)'와 같은 것을 사용하면 루프의 반복마다 숫자의 SQRT를 다시 계산합니다.
몇 가지 다른 방법을 피할 수 있습니다. 루프 전에 SQRT를 사전 컴퓨팅하고 루프 조건에서 사전 계산 된 값을 사용하거나 다른 방향으로 작동하고 변경할 수 있습니다. i<Math.sqrt(x) 에게 i*i<x. 개인적으로, 나는 제곱근을 미리 컴퓨팅하지만-나는 그것이 더 명확하고 조금 더 빠르다고 생각하지만, 이는 루프의 반복 횟수에 따라 다릅니다. i*i 루프에서 여전히 곱셈을 수행하고 있음을 의미합니다). 몇 번의 반복만으로 i*i 일반적으로 더 빠릅니다. 충분한 반복으로 손실 i*i 모든 반복은 실행 시간보다 중요합니다 sqrt 루프 밖에서.
이는 아마도 당신이 다루는 숫자의 크기에 적합 할 것입니다. 15 자리 제한은 제곱근이 7 또는 8 자리임을 의미하며, 이는 상당히 합리적인 메모리에 맞습니다. 반면 에이 범위의 숫자를 많이 처리하려면 더 정교한 프라임 체크 알고리즘을보고 싶을 수도 있습니다. Pollard 또는 Brent의 알고리즘. 이것들은 더 복잡하지만 (가볍게두기 위해) 많은 많은 수의 경우 더 빠릅니다.
더 큰 숫자에 대한 다른 알고리즘이 있습니다 (2 차 체, 일반 번호 필드 체) 그러나 우리는 지금 그들에게 들어 가지 않을 것입니다. 그들은 훨씬 더 복잡하고 실제로 큰 숫자를 다루는 데 유용합니다 (GNFS는 100 숫자 범위에서 유용하기 시작합니다).
첫 번째 단계: 입력이 프라임인지 확인하기 위해 확장 방법을 작성하십시오.
public static bool isPrime(this int number ) {
for (int i = 2; i < number; i++) {
if (number % i == 0) {
return false;
}
}
return true;
}
2 단계 : 0에서 숫자 입력 사이의 모든 소수를 인쇄하는 메소드를 작성하십시오.
public static void getAllPrimes(int number)
{
for (int i = 0; i < number; i++)
{
if (i.isPrime()) Console.WriteLine(i);
}
}
그것은 단지 내 의견일 수도 있지만 귀하의 프로그램에는 또 다른 심각한 오류가 있습니다(주어진 '소수' 질문은 제쳐두고 철저하게 답변되었습니다).
나머지 응답자들과 마찬가지로 나는 이것이 당신이 (아마도) 개발자가 되고 싶다는 것을 나타내는 숙제라고 가정합니다.
코드를 분류하는 방법을 배워야 합니다.프로젝트에서 항상 수행해야 하는 작업은 아니지만 수행 방법을 아는 것이 좋습니다.
귀하의 방법 prime_num(long num) 은 더 좋고 설명적인 이름을 가질 수 있습니다.그리고 주어진 숫자보다 작은 모든 소수를 찾으려면 이를 목록으로 반환해야 합니다.이렇게 하면 디스플레이와 기능을 더 쉽게 분리할 수 있습니다.
단순히 소수가 포함된 IList를 반환한 경우 해당 소수를 기본 함수에 표시하거나(예를 들어 인쇄하기 위해 다른 외부 함수를 호출) 이후 추가 계산에 사용할 수 있습니다.
그래서 제가 여러분에게 가장 추천하는 것은 다음과 같이 하는 것입니다.
public void main(string args[])
{
//Get the number you want to use as input
long x = number;//'number' can be hard coded or retrieved from ReadLine() or from the given arguments
IList<long> primes = FindSmallerPrimes(number);
DisplayPrimes(primes);
}
public IList<long> FindSmallerPrimes(long largestNumber)
{
List<long> returnList = new List<long>();
//Find the primes, using a method as described by another answer, add them to returnList
return returnList;
}
public void DisplayPrimes(IList<long> primes)
{
foreach(long l in primes)
{
Console.WriteLine ( "Prime:" + l.ToString() );
}
}
이런 분리가 필요하지 않은 곳에서 일하게 되더라도 어떻게 해야 하는지 알아두는 것이 좋습니다.
편집_추가: Will Ness가 맞다면 질문의 목적은 프로그램이 실행되는 동안(일시 정지하려면 Pause/Break를 누르고 다시 시작하려면 아무 키나 누르십시오) 연속적인 소수 스트림을 출력하는 것뿐이며 모든 사람이 그 상한값에 도달할 것이라는 심각한 희망은 없습니다. 제한이 있는 경우 상한 인수 없이 첫 번째 'i' for 루프에 대해 "true" 범위 검사를 사용하여 코드를 작성해야 합니다.반면에 질문이 실제로 소수를 한도까지 인쇄하려는 경우 다음 코드는 메모리를 전혀 사용하지 않는다는 장점과 함께 홀수에 대해서만 시행 분할을 사용하여 작업을 훨씬 더 효율적으로 수행합니다. (위와 같이 연속 루프로 변환할 수도 있습니다):
static void primesttt(ulong top_number) {
Console.WriteLine("Prime: 2");
for (var i = 3UL; i <= top_number; i += 2) {
var isPrime = true;
for (uint j = 3u, lim = (uint)Math.Sqrt((double)i); j <= lim; j += 2) {
if (i % j == 0) {
isPrime = false;
break;
}
}
if (isPrime) Console.WriteLine("Prime: {0} ", i);
}
}
첫째, 질문 코드는 루프 변수가 정수이고 테스트된 한계가 거대한 긴 정수이기 때문에 출력을 생성하지 않습니다. 즉, 루프가 내부 루프를 생성하는 한계에 도달하는 것이 불가능하다는 것을 의미합니다. 편집됨: 변수 'j'는 음수로 다시 돌아갑니다.'j' 변수가 -1로 돌아오면 테스트된 숫자는 모든 숫자가 -1로 균등하게 나누어지기 때문에 소수 테스트에 실패합니다. END_EDIT.이것이 수정되더라도 질문 코드는 매우 많은 양의 합성수(모든 짝수 + 홀수 합성수)를 해당 상단까지의 전체 숫자 범위로 64비트 나누기로 묶여 있기 때문에 매우 느린 출력을 생성합니다. 그것이 생산할 수 있는 각 소수에 대해 10의 수를 16제곱합니다.위 코드는 계산을 홀수로만 제한하고 제곱근까지만 모듈로 나눗셈을 수행하기 때문에 작동합니다. 현재 테스트 중인 숫자.
최대 10억 개의 소수를 표시하는 데 한 시간 정도 걸리므로 특히 계산 속도가 느려질수록 모든 소수를 10,000조(10의 16승)로 표시하는 데 걸리는 시간을 상상할 수 있습니다. 범위가 증가하면서. END_EDIT_ADD
Linq를 사용하는 @SLaks의 하나의 라이너(일종) 답변이 작동하지만 실제로는 최적화되지 않은 버전이므로 실제로 에라토스테네스의 체는 아닙니다. 시범사업부, 홀수 소수를 제거하지 않고, 발견된 기본 소수의 제곱에서 시작하지 않으며, 체로 걸러낼 최상위 숫자의 제곱근보다 큰 기본 소수에 대한 컬링을 중지하지 않는다는 점에서 최적화되지 않았습니다.또한 다중 중첩 열거 작업으로 인해 속도가 매우 느립니다.
이는 실제로 Linq Aggregate 방법을 남용하는 것이며 생성된 두 Linq Range 중 첫 번째를 효과적으로 사용하지 않습니다.다음과 같이 열거 오버헤드가 적은 최적화된 평가판 분할이 될 수 있습니다.
static IEnumerable<int> primes(uint top_number) {
var cullbf = Enumerable.Range(2, (int)top_number).ToList();
for (int i = 0; i < cullbf.Count; i++) {
var bp = cullbf[i]; var sqr = bp * bp; if (sqr > top_number) break;
cullbf.RemoveAll(c => c >= sqr && c % bp == 0);
} return cullbf; }
SLaks 답변보다 몇 배 더 빠르게 실행됩니다.그러나 목록 생성, 다중 열거 및 다중 나누기(모듈로에 의해 암시됨) 작업으로 인해 여전히 느리고 메모리 집약적입니다.
다음의 실제 에라토스테네스의 체 구현은 체질된 숫자당 1비트 표현만 사용하고 열거를 최종 반복기 시퀀스 출력으로 제한할 뿐만 아니라 홀수 복합물만 처리하도록 최적화되어 있기 때문에 약 30배 더 빠르게 실행되고 훨씬 적은 메모리를 사용합니다. 다음과 같이 기본 소수에 대한 기본 소수의 제곱에서 최대 수의 제곱근까지만 선별합니다.
static IEnumerable<uint> primes(uint top_number) {
if (top_number < 2u) yield break;
yield return 2u; if (top_number < 3u) yield break;
var BFLMT = (top_number - 3u) / 2u;
var SQRTLMT = ((uint)(Math.Sqrt((double)top_number)) - 3u) / 2u;
var buf = new BitArray((int)BFLMT + 1,true);
for (var i = 0u; i <= BFLMT; ++i) if (buf[(int)i]) {
var p = 3u + i + i; if (i <= SQRTLMT) {
for (var j = (p * p - 3u) / 2u; j <= BFLMT; j += p)
buf[(int)j] = false; } yield return p; } }
위 코드는 Intel i7-2700K(3.5GHz)에서 약 77밀리초 내에 천만 범위의 모든 소수를 계산합니다.
다음과 같이 using 문과 정적 Main 메서드를 사용하여 두 정적 메서드 중 하나를 호출하고 테스트할 수 있습니다.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
static void Main(string[] args) {
Console.WriteLine("This program generates prime sequences.\r\n");
var n = 10000000u;
var elpsd = -DateTime.Now.Ticks;
var count = 0; var lastp = 0u;
foreach (var p in primes(n)) { if (p > n) break; ++count; lastp = (uint)p; }
elpsd += DateTime.Now.Ticks;
Console.WriteLine(
"{0} primes found <= {1}; the last one is {2} in {3} milliseconds.",
count, n, lastp,elpsd / 10000);
Console.Write("\r\nPress any key to exit:");
Console.ReadKey(true);
Console.WriteLine();
}
이는 수열에서 한계까지의 소수 수, 마지막으로 발견된 소수, 그리고 그까지 열거하는 데 소요된 시간을 표시합니다.
편집_추가: 그러나 질문에서 요구하는 대로 10,000조(10의 16승) 미만의 소수 수의 열거를 생성하려면 멀티 코어 처리를 사용하는 분할된 페이지 접근 방식이 필요하지만 C++ 및 매우 고도로 최적화된 PrimeSieve, 이것은 발견된 소수의 수를 생성하는 데 400시간 이상이 필요하고, 모든 소수를 열거하는 데는 수십 배의 시간이 소요되므로 질문에서 요구하는 작업을 수행하는 데 1년이 넘게 걸립니다.시도된 최적화되지 않은 시행 분할 알고리즘을 사용하여 이를 수행하려면 10000000년(즉, 200만 0년)과 같이 최적화된 시행 분할 알고리즘을 사용하더라도 매우 오랜 시간이 걸릴 것입니다!! !).
그가 그것을 시도했을 때 그의 데스크톱 컴퓨터가 그냥 앉아서 멈춘 것은 별로 놀라운 일이 아닙니다!!!!100만과 같은 더 작은 범위를 시도하더라도 구현된 대로 몇 초 정도가 걸린다는 것을 알았을 것입니다.
여기에 게시한 솔루션은 마지막 에라토스테네스의 체라도 해당 범위에 약 640테라바이트의 메모리가 필요하기 때문에 문제가 되지 않습니다.
이것이 바로 PrimeSieve와 같은 페이지 분할 접근 방식만이 지정된 범위에 대해 이러한 종류의 문제를 처리할 수 있는 이유이며, 심지어 슈퍼 컴퓨터에 액세스하지 않는 한 몇 주에서 몇 년까지 매우 오랜 시간이 필요한 이유입니다. 수십만 개의 코어. END_EDIT_ADD
더 많은 숙제 냄새가납니다. 내 아주 오래된 그래프 계산기는 이와 같은 주요 프로그램이 있습니다. 기술적으로 내부 Devision Checking 루프는 i^(1/2)로만 실행되면됩니다. 0과 L 사이의 "모든"소수를 찾아야합니까? 또 다른 주요 문제는 루프 변수가 "int"인 반면 입력 데이터는 "긴"이므로 오버플로로 인해 루프가 한 번도 실행되지 않습니다. 루프 변수를 수정하십시오.
C#의 한 줄 코드 :-
Console.WriteLine(String.Join(Environment.NewLine,
Enumerable.Range(2, 300)
.Where(n => Enumerable.Range(2, (int)Math.Sqrt(n) - 1)
.All(nn => n % nn != 0)).ToArray()));
그만큼 에라 토스 테네스의 체 위의 답변은 정확하지 않습니다. 기록 된대로 1 ~ 1000000 사이의 모든 프라임을 찾을 수 있습니다. 1과 NUM 사용 사이의 모든 프라임을 찾으려면 다음과 같습니다.
private static IEnumerable Primes01(int num)
{
return Enumerable.Range(1, Convert.ToInt32(Math.Floor(Math.Sqrt(num))))
.Aggregate(Enumerable.Range(1, num).ToList(),
(result, index) =>
{
result.RemoveAll(i => i > result[index] && i%result[index] == 0);
return result;
}
);
}
이 목록에는 최종 프라임 목록이 포함되므로 집계의 씨앗은 범위 1에서 num이어야합니다. 그만큼 Enumerable.Range(1, Convert.ToInt32(Math.Floor(Math.Sqrt(num)))) 씨앗이 제거되는 횟수입니다.
ExchangeCore 포럼 찾은 프라임을 파일에 쓰는 것으로 보이는 좋은 콘솔 애플리케이션이 나열되어 있으므로, 동일한 파일을 시작점과 같은 파일을 사용할 수 있으므로 2에서 프라임 찾기를 다시 시작할 필요가 없으며 해당 파일의 다운로드를 제공 할 수 있습니다. 모든 발견 된 프라임으로 최대 1 억이므로 좋은 출발이 될 것입니다.
페이지의 알고리즘은 또한 몇 개의 바로 가기 (홀수 및 제곱근에만 체크인)를 사용하여 매우 효율적이며 긴 숫자를 계산할 수 있습니다.
그래서 이것은 기본적으로입니다 오타 두 개만, 하나, 가장 불행한 것, for (int j = 2; j <= num; j++) 비생산적인 테스트의 이유입니다 1%2,1%3 ... 1%(10^15-1) 오랫동안 계속해서 OP가 얻지 못했습니다. "모든 출력". 그랬어야 했어 j < i; 대신에. 다른 하나, 사소한 사람은 i 0이 아닌 2에서 시작해야합니다.
for( i=2; i <= num; i++ )
{
for( j=2; j < i; j++ ) // j <= sqrt(i) is really enough
....
분명히 그것은 합리적으로 기대할 수 없습니다 콘솔 인쇄 합리적인 타임 프레임으로 완료 될 28 조의 프라임 중. 따라서 문제의 원래 의도는 분명히 꾸준한 프라임 스트림을 인쇄하는 것이 었습니다. 무기한. 따라서 Eratosthenes의 체를 간단하게 사용하는 것을 제안하는 모든 솔루션은 여기에 전적으로 공로가 없습니다. 단순한 Eratosthenes의 체가 제한되어 있습니다 - 한계는 미리 설정되어야합니다.
여기서 작동 할 수있는 것은 최적화 된 시험 부문으로, 프라임을 찾을 수있는 프라임을 절약하고 후보 아래의 모든 숫자뿐만 아니라 프라임에 대한 테스트입니다.
두 번째 대안은 훨씬 더 나은 복잡성 (예 : 훨씬 더 빠른)을 사용하는 것입니다. 에라토스테네스의 세그먼트 된 체. 점진적이고 무한한 것입니다.
이 두 가지 체계는 모두 사용할 것입니다 프라임의 이중 단계 생산: 하나는 첫 번째 단계의 한계보다 훨씬 높은 테스트 (또는 체질)에서 다른 단계에서 사용하기 위해 프라임을 생성하고 저장합니다. 점점 더 위로).
솔직히 말하면, 제안 된 솔루션 중 일부는 실제로 느리기 때문에 나쁜 제안입니다. 단일 번호를 프라임으로 테스트하려면 일부 분할/모듈로 연산자가 필요하지만 범위를 계산하려면 필요하지 않습니다.
기본적으로 당신은 (정의에 따라) 프라임 자체가 아닌 이전에 발견 된 프라임의 배수 인 숫자를 제외합니다.
쉽게 구현할 수는 없으므로 의사 코드의 접근 방식입니다. (내 컴퓨터에서 실제 구현은 8 초 내에 sytem.int32 (2 bilion)의 모든 프라임을 계산합니다.
public IEnumerable<long> GetPrimes(long max)
{
// we safe the result set in an array of bytes.
var buffer = new byte[long >> 4];
// 1 is not a prime.
buffer[0] = 1;
var iMax = (long)Math.Sqrt(max);
for(long i = 3; i <= iMax; i +=2 )
{
// find the index in the buffer
var index = i >> 4;
// find the bit of the buffer.
var bit = (i >> 1) & 7;
// A not set bit means: prime
if((buffer[index] & (1 << bit)) == 0)
{
var step = i << 2;
while(step < max)
{
// find position in the buffer to write bits that represent number that are not prime.
}
}
// 2 is not in the buffer.
yield return 2;
// loop through buffer and yield return odd primes too.
}
}
솔루션은 비트 동작에 대한 이해가 필요합니다. 그러나 그것은 더 빠른 방법과 방법입니다. 나중에 사용하기 위해 필요한 경우 디스크 결과 결과를 안전하게 안전하게 만들 수 있습니다. 17 * 10^9 숫자의 결과는 1GB로 안전 할 수 있으며 해당 결과 세트의 계산은 최대 2 분이 걸립니다.
나는 이것이 조용한 오래된 질문이라는 것을 알고 있지만 여기를 읽은 후 :Eratosthenes 위키의 체
이것이 내가 알고리즘을 이해함으로써 쓴 방식입니다.
void SieveOfEratosthenes(int n)
{
bool[] primes = new bool[n + 1];
for (int i = 0; i < n; i++)
primes[i] = true;
for (int i = 2; i * i <= n; i++)
if (primes[i])
for (int j = i * 2; j <= n; j += i)
primes[j] = false;
for (int i = 2; i <= n; i++)
if (primes[i]) Console.Write(i + " ");
}
첫 번째 루프에서 우리는 부울 배열을 True로 채 웁니다.
루프의 두 번째는 1이 소수가 아니기 때문에 2에서 시작합니다. 소수가 아직 변경되지 않은지 확인한 다음 j의 색인에 false를 할당합니다.
마지막 루프 우리는 그것이 프라임 일 때 단지 인쇄합니다.
매우 유사한 - 운동에서 C#에서 Eratosthenes의 체를 구현하기위한 것입니다.
public class PrimeFinder
{
readonly List<long> _primes = new List<long>();
public PrimeFinder(long seed)
{
CalcPrimes(seed);
}
public List<long> Primes { get { return _primes; } }
private void CalcPrimes(long maxValue)
{
for (int checkValue = 3; checkValue <= maxValue; checkValue += 2)
{
if (IsPrime(checkValue))
{
_primes.Add(checkValue);
}
}
}
private bool IsPrime(long checkValue)
{
bool isPrime = true;
foreach (long prime in _primes)
{
if ((checkValue % prime) == 0 && prime <= Math.Sqrt(checkValue))
{
isPrime = false;
break;
}
}
return isPrime;
}
}
프라임 헬퍼 매우 빠른 계산
public static class PrimeHelper
{
public static IEnumerable<Int32> FindPrimes(Int32 maxNumber)
{
return (new PrimesInt32(maxNumber));
}
public static IEnumerable<Int32> FindPrimes(Int32 minNumber, Int32 maxNumber)
{
return FindPrimes(maxNumber).Where(pn => pn >= minNumber);
}
public static bool IsPrime(this Int64 number)
{
if (number < 2)
return false;
else if (number < 4 )
return true;
var limit = (Int32)System.Math.Sqrt(number) + 1;
var foundPrimes = new PrimesInt32(limit);
return !foundPrimes.IsDivisible(number);
}
public static bool IsPrime(this Int32 number)
{
return IsPrime(Convert.ToInt64(number));
}
public static bool IsPrime(this Int16 number)
{
return IsPrime(Convert.ToInt64(number));
}
public static bool IsPrime(this byte number)
{
return IsPrime(Convert.ToInt64(number));
}
}
public class PrimesInt32 : IEnumerable<Int32>
{
private Int32 limit;
private BitArray numbers;
public PrimesInt32(Int32 limit)
{
if (limit < 2)
throw new Exception("Prime numbers not found.");
startTime = DateTime.Now;
calculateTime = startTime - startTime;
this.limit = limit;
try { findPrimes(); } catch{/*Overflows or Out of Memory*/}
calculateTime = DateTime.Now - startTime;
}
private void findPrimes()
{
/*
The Sieve Algorithm
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
*/
numbers = new BitArray(limit, true);
for (Int32 i = 2; i < limit; i++)
if (numbers[i])
for (Int32 j = i * 2; j < limit; j += i)
numbers[j] = false;
}
public IEnumerator<Int32> GetEnumerator()
{
for (Int32 i = 2; i < 3; i++)
if (numbers[i])
yield return i;
if (limit > 2)
for (Int32 i = 3; i < limit; i += 2)
if (numbers[i])
yield return i;
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
// Extended for Int64
public bool IsDivisible(Int64 number)
{
var sqrt = System.Math.Sqrt(number);
foreach (var prime in this)
{
if (prime > sqrt)
break;
if (number % prime == 0)
{
DivisibleBy = prime;
return true;
}
}
return false;
}
private static DateTime startTime;
private static TimeSpan calculateTime;
public static TimeSpan CalculateTime { get { return calculateTime; } }
public Int32 DivisibleBy { get; set; }
}
public static void Main()
{
Console.WriteLine("enter the number");
int i = int.Parse(Console.ReadLine());
for (int j = 2; j <= i; j++)
{
for (int k = 2; k <= i; k++)
{
if (j == k)
{
Console.WriteLine("{0}is prime", j);
break;
}
else if (j % k == 0)
{
break;
}
}
}
Console.ReadLine();
}
static void Main(string[] args)
{ int i,j;
Console.WriteLine("prime no between 1 to 100");
for (i = 2; i <= 100; i++)
{
int count = 0;
for (j = 1; j <= i; j++)
{
if (i % j == 0)
{ count=count+1; }
}
if ( count <= 2)
{ Console.WriteLine(i); }
}
Console.ReadKey();
}
u는 일반 소수 개념을 사용할 수 있습니다. 개념은 두 가지 요소 (하나와 그 자체) 만 필요합니다. 쉬운 방법을 좋아합니다
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace PrimeNUmber
{
class Program
{
static void FindPrimeNumber(long num)
{
for (long i = 1; i <= num; i++)
{
int totalFactors = 0;
for (int j = 1; j <= i; j++)
{
if (i % j == 0)
{
totalFactors = totalFactors + 1;
}
}
if (totalFactors == 2)
{
Console.WriteLine(i);
}
}
}
static void Main(string[] args)
{
long num;
Console.WriteLine("Enter any value");
num = Convert.ToInt64(Console.ReadLine());
FindPrimeNumber(num);
Console.ReadLine();
}
}
}
이 솔루션은 0과 100 사이의 모든 소수를 표시합니다.
int counter = 0;
for (int c = 0; c <= 100; c++)
{
counter = 0;
for (int i = 1; i <= c; i++)
{
if (c % i == 0)
{ counter++; }
}
if (counter == 2)
{ Console.Write(c + " "); }
}
이것은 C#에서 소수를 계산하는 가장 빠른 방법입니다.
void PrimeNumber(long number)
{
bool IsprimeNumber = true;
long value = Convert.ToInt32(Math.Sqrt(number));
if (number % 2 == 0)
{
IsprimeNumber = false;
}
for (long i = 3; i <= value; i=i+2)
{
if (number % i == 0)
{
// MessageBox.Show("It is divisible by" + i);
IsprimeNumber = false;
break;
}
}
if (IsprimeNumber)
{
MessageBox.Show("Yes Prime Number");
}
else
{
MessageBox.Show("No It is not a Prime NUmber");
}
}
class CheckIfPrime
{
static void Main()
{
while (true)
{
Console.Write("Enter a number: ");
decimal a = decimal.Parse(Console.ReadLine());
decimal[] k = new decimal[int.Parse(a.ToString())];
decimal p = 0;
for (int i = 2; i < a; i++)
{
if (a % i != 0)
{
p += i;
k[i] = i;
}
else
p += i;
}
if (p == k.Sum())
{ Console.WriteLine ("{0} is prime!", a);}
else
{Console.WriteLine("{0} is NOT prime", a);}
}
}
}
알고리즘을 구현하는 매우 최적의 방법이 있습니다. 그러나 수학에 대해 많이 알지 못하고 단순히 프라임의 정의를 요구 사항으로 간단히 따르는 경우 : 1 만 (그리고 그 자체로 만 나눌 수있는 숫자), 여기에는 양수에 대한 코드를 이해하는 것이 간단합니다.
public bool IsPrime(int candidateNumber)
{
int fromNumber = 2;
int toNumber = candidateNumber - 1;
while(fromNumber <= toNumber)
{
bool isDivisible = candidateNumber % fromNumber == 0;
if (isDivisible)
{
return false;
}
fromNumber++;
}
return true;
}
모든 숫자는 1으로 나눌 수 있고 그 자체로는 2에서 2에서 그 자체 직전에 숫자까지 확인하기 시작합니다. 그것이 기본적인 추론입니다.
당신은 이것도 할 수 있습니다 :
class Program
{
static void Main(string[] args)
{
long numberToTest = 350124;
bool isPrime = NumberIsPrime(numberToTest);
Console.WriteLine(string.Format("Number {0} is prime? {1}", numberToTest, isPrime));
Console.ReadLine();
}
private static bool NumberIsPrime(long n)
{
bool retVal = true;
if (n <= 3)
{
retVal = n > 1;
} else if (n % 2 == 0 || n % 3 == 0)
{
retVal = false;
}
int i = 5;
while (i * i <= n)
{
if (n % i == 0 || n % (i + 2) == 0)
{
retVal = false;
}
i += 6;
}
return retVal;
}
}
