C-숫자가 소수인지 확인
정수를 취하고 부울을 반환하여 숫자가 소수인지 아닌지 그리고 C를 많이 알지 못하는 방법을 생각해 내려고합니다. 누구든지 나에게 몇 가지 조언을 해줄까요?
기본적으로 다음과 같이 C #에서이 작업을 수행합니다.
static bool IsPrime(int number)
{
for (int i = 2; i < number; i++)
{
if (number % i == 0 && i != number)
return false;
}
return true;
}
좋아, C는 잊어 버려. 내가 숫자를주고 그것이 소수인지 결정하도록 요청한다고 가정하자. 어떻게하나요? 단계를 명확하게 기록한 다음 코드로 변환하는 것에 대해 걱정 하십시오 .
알고리즘을 결정하면 프로그램 작성 방법을 파악하고 다른 사람들이이를 도와 줄 수있는 방법을 훨씬 쉽게 파악할 수 있습니다.
편집 : 게시 한 C # 코드는 다음과 같습니다.
static bool IsPrime(int number) {
for (int i = 2; i < number; i++) {
if (number % i == 0 && i != number) return false;
}
return true;
}
이것은 거의 유효한 C입니다. 거기에는 없다 bool타입 C에없고 true또는 false당신이 그것을 조금 수정해야하므로, (편집 : 크리스토퍼 존슨이 제대로 C99은 stdbool.h 헤더를 추가 한 지적). 어떤 사람들은 C99 환경에 액세스 할 수 없기 때문에 (하지만 하나를 사용해야합니다!) 아주 사소한 변경을하겠습니다.
int IsPrime(int number) {
int i;
for (i=2; i<number; i++) {
if (number % i == 0 && i != number) return 0;
}
return 1;
}
이것은 당신이 원하는 것을 수행하는 완벽하게 유효한 C 프로그램입니다. 너무 많은 노력없이 조금 개선 할 수 있습니다. 첫째, i항상보다 작 number으므로 i != number항상 성공 하는 검사입니다 . 제거 할 수 있습니다.
또한 실제로 제수를 사용할 필요가 없습니다 number - 1. sqrt (number)에 도달하면 확인을 중지 할 수 있습니다. 때문에 sqrt부동 소수점 연산이며, 그 미묘 전체 더미를 제공, 우리가 실제로 계산되지 않습니다 sqrt(number). 대신 다음 사항을 확인할 수 있습니다 i*i <= number.
int IsPrime(int number) {
int i;
for (i=2; i*i<=number; i++) {
if (number % i == 0) return 0;
}
return 1;
}
그래도 마지막 한 가지; 원래 알고리즘에 작은 버그가있었습니다! 경우 number네거티브 또는 영 또는 하나,이 함수 수가 소수 주장한다. 이를 올바르게 처리하고 싶을 수 number있으며 양수 값에만 관심이 많기 때문에 서명되지 않은 상태 로 만들 수 있습니다.
int IsPrime(unsigned int number) {
if (number <= 1) return 0; // zero and one are not prime
unsigned int i;
for (i=2; i*i<=number; i++) {
if (number % i == 0) return 0;
}
return 1;
}
이것은 숫자가 소수인지 확인하는 가장 빠른 방법은 아니지만 작동하며 매우 간단합니다. 코드를 거의 수정할 필요가 없었습니다!
아무도 이것을 언급하지 않았다는 것이 놀랍습니다.
에라토스테네스 체 사용
세부:
- 기본적으로 소수가 아닌 숫자는 1과 그 자체 외에 다른 숫자로 나눌 수 있습니다.
- 따라서 소수가 아닌 숫자는 소수의 곱이됩니다.
에라토스테네스의 체는 소수를 찾아 저장합니다. 새 숫자가 소수인지 확인하면 이전 소수가 모두 알려진 소수 목록에 대해 확인됩니다.
원인:
- 이 알고리즘 / 문제는 " Embarrassingly Parallel " 로 알려져 있습니다.
- 소수 집합을 만듭니다.
- 동적 프로그래밍 문제의 예
- 빠르다!
Stephen Canon은 그것에 대해 아주 잘 대답했습니다!
그러나
- 알고리즘은 2와 3을 제외하고 모든 소수가 6k ± 1 형식임을 관찰함으로써 더욱 개선 될 수 있습니다.
- 이는 모든 정수가 일부 정수 k 및 i = -1, 0, 1, 2, 3 또는 4에 대해 (6k + i)로 표현 될 수 있기 때문입니다. 2 나누기 (6k + 0), (6k + 2), (6k + 4); 그리고 3 분할 (6k + 3).
- 따라서보다 효율적인 방법은 n이 2 또는 3으로 나눌 수 있는지 테스트 한 다음 6k ± 1 ≤ √n 형식의 모든 숫자를 확인하는 것입니다.
이것은 모든 m을 √n까지 테스트하는 것보다 3 배 빠릅니다.
int IsPrime(unsigned int number) { if (number <= 3 && number > 1) return 1; // as 2 and 3 are prime else if (number%2==0 || number%3==0) return 0; // check if number is divisible by 2 or 3 else { unsigned int i; for (i=5; i*i<=number; i+=6) { if (number % i == 0 || number%(i + 2) == 0) return 0; } return 1; } }
- 작은 소수로 구성된 표를 만들고 입력 된 숫자를 나누는 지 확인합니다.
- 숫자가 1까지 유지되면 기저를 늘리면서 의사 소수성 검정을 시도하십시오. 예를 들어 Miller-Rabin 소수 검정 을 참조하십시오 .
- 당신의 숫자가 2까지 살아남 았다면, 그것이 잘 알려진 경계 아래에 있으면 소수라고 결론을 내릴 수 있습니다. 그렇지 않으면 귀하의 대답은 "아마도 소수"일 것입니다. 위키 페이지에서 이러한 경계에 대한 몇 가지 값을 찾을 수 있습니다.
이 프로그램은 소수 검사를 위해 단일 숫자를 검사하는 데 훨씬 효율적입니다.
bool check(int n){
if (n <= 3) {
return n > 1;
}
if (n % 2 == 0 || n % 3 == 0) {
return false;
}
int sq=sqrt(n); //include math.h or use i*i<n in for loop
for (int i = 5; i<=sq; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
2에서 확인중인 숫자의 근까지 각 정수의 계수를 확인합니다.
계수가 0이면 소수가 아닙니다.
의사 코드 :
bool IsPrime(int target)
{
for (i = 2; i <= root(target); i++)
{
if ((target mod i) == 0)
{
return false;
}
}
return true;
}
이 질문을 읽은 후 일부 답변이 2 * 3 = 6의 배수로 루프를 실행하여 최적화를 제공한다는 사실에 흥미를 느꼈습니다.
그래서 같은 아이디어로 2 * 3 * 5 = 30의 배수로 새로운 함수를 만듭니다.
int check235(unsigned long n)
{
unsigned long sq, i;
if(n<=3||n==5)
return n>1;
if(n%2==0 || n%3==0 || n%5==0)
return 0;
if(n<=30)
return checkprime(n); /* use another simplified function */
sq=ceil(sqrt(n));
for(i=7; i<=sq; i+=30)
if (n%i==0 || n%(i+4)==0 || n%(i+6)==0 || n%(i+10)==0 || n%(i+12)==0
|| n%(i+16)==0 || n%(i+22)==0 || n%(i+24)==0)
return 0;
return 1;
}
두 기능을 모두 실행하고 시간을 확인함으로써이 기능이 정말 빠르다는 것을 알 수 있습니다. 2 개의 다른 소수를 가진 2 개의 테스트를 봅시다 :
$ time ./testprimebool.x 18446744069414584321 0
f(2,3)
Yes, its prime.
real 0m14.090s
user 0m14.096s
sys 0m0.000s
$ time ./testprimebool.x 18446744069414584321 1
f(2,3,5)
Yes, its prime.
real 0m9.961s
user 0m9.964s
sys 0m0.000s
$ time ./testprimebool.x 18446744065119617029 0
f(2,3)
Yes, its prime.
real 0m13.990s
user 0m13.996s
sys 0m0.004s
$ time ./testprimebool.x 18446744065119617029 1
f(2,3,5)
Yes, its prime.
real 0m10.077s
user 0m10.068s
sys 0m0.004s
그래서 나는 일반화하면 누군가가 너무 많이 얻을 것이라고 생각했습니다. 먼저 주어진 원시 소수 목록을 정리하기 위해 포위 공격을 수행 한 다음이 목록을 사용하여 더 큰 소수를 계산하는 함수를 생각해 냈습니다.
int checkn(unsigned long n, unsigned long *p, unsigned long t)
{
unsigned long sq, i, j, qt=1, rt=0;
unsigned long *q, *r;
if(n<2)
return 0;
for(i=0; i<t; i++)
{
if(n%p[i]==0)
return 0;
qt*=p[i];
}
qt--;
if(n<=qt)
return checkprime(n); /* use another simplified function */
if((q=calloc(qt, sizeof(unsigned long)))==NULL)
{
perror("q=calloc()");
exit(1);
}
for(i=0; i<t; i++)
for(j=p[i]-2; j<qt; j+=p[i])
q[j]=1;
for(j=0; j<qt; j++)
if(q[j])
rt++;
rt=qt-rt;
if((r=malloc(sizeof(unsigned long)*rt))==NULL)
{
perror("r=malloc()");
exit(1);
}
i=0;
for(j=0; j<qt; j++)
if(!q[j])
r[i++]=j+1;
free(q);
sq=ceil(sqrt(n));
for(i=1; i<=sq; i+=qt+1)
{
if(i!=1 && n%i==0)
return 0;
for(j=0; j<rt; j++)
if(n%(i+r[j])==0)
return 0;
}
return 1;
}
코드를 최적화하지 않았다고 생각하지만 공정합니다. 자, 테스트. 동적 메모리가 너무 많기 때문에 목록 2 3 5가 하드 코딩 된 2 3 5보다 약간 느릴 것으로 예상했습니다. 그러나 아래에서 볼 수 있듯이 괜찮 았습니다. 그 후 시간이 점점 줄어들어 최고의 목록이 완성되었습니다.
2 3 5 7 11 13 17 19
8.6 초로. 따라서 누군가가 그러한 기술을 사용하는 하드 코딩 된 프로그램을 작성한다면 이득이 그다지 크지 않기 때문에 목록 2 3 및 5를 사용하는 것이 좋습니다. 또한 코드를 작성하려는 경우이 목록은 괜찮습니다. 문제는 루프없이 모든 경우를 명시 할 수있다, 또는 코드 (1658879있을 것이다 매우 큰 것 ORs입니다, ||각각의 내부에서 if). 다음 목록 :
2 35 7 11 13 17 19 23
시간은 13 초로 더 커지기 시작했습니다. 여기 전체 테스트 :
$ time ./testprimebool.x 18446744065119617029 2 3 5
f(2,3,5)
Yes, its prime.
real 0m12.668s
user 0m12.680s
sys 0m0.000s
$ time ./testprimebool.x 18446744065119617029 2 3 5 7
f(2,3,5,7)
Yes, its prime.
real 0m10.889s
user 0m10.900s
sys 0m0.000s
$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11
f(2,3,5,7,11)
Yes, its prime.
real 0m10.021s
user 0m10.028s
sys 0m0.000s
$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13
f(2,3,5,7,11,13)
Yes, its prime.
real 0m9.351s
user 0m9.356s
sys 0m0.004s
$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17
f(2,3,5,7,11,13,17)
Yes, its prime.
real 0m8.802s
user 0m8.800s
sys 0m0.008s
$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17 19
f(2,3,5,7,11,13,17,19)
Yes, its prime.
real 0m8.614s
user 0m8.564s
sys 0m0.052s
$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17 19 23
f(2,3,5,7,11,13,17,19,23)
Yes, its prime.
real 0m13.013s
user 0m12.520s
sys 0m0.504s
$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17 19 23 29
f(2,3,5,7,11,13,17,19,23,29)
q=calloc(): Cannot allocate memory
추신. 프로그램이 종료 되 자마자 메모리가 해제되어 시간을 벌기 때문에 의도적으로 해제하지 않았습니다.이 작업을 OS에 제공했습니다. 그러나 계산 후에도 코드를 계속 실행하려면 해제하는 것이 좋습니다.
보너스
int check2357(unsigned long n)
{
unsigned long sq, i;
if(n<=3||n==5||n==7)
return n>1;
if(n%2==0 || n%3==0 || n%5==0 || n%7==0)
return 0;
if(n<=210)
return checkprime(n); /* use another simplified function */
sq=ceil(sqrt(n));
for(i=11; i<=sq; i+=210)
{
if(n%i==0 || n%(i+2)==0 || n%(i+6)==0 || n%(i+8)==0 || n%(i+12)==0 ||
n%(i+18)==0 || n%(i+20)==0 || n%(i+26)==0 || n%(i+30)==0 || n%(i+32)==0 ||
n%(i+36)==0 || n%(i+42)==0 || n%(i+48)==0 || n%(i+50)==0 || n%(i+56)==0 ||
n%(i+60)==0 || n%(i+62)==0 || n%(i+68)==0 || n%(i+72)==0 || n%(i+78)==0 ||
n%(i+86)==0 || n%(i+90)==0 || n%(i+92)==0 || n%(i+96)==0 || n%(i+98)==0 ||
n%(i+102)==0 || n%(i+110)==0 || n%(i+116)==0 || n%(i+120)==0 || n%(i+126)==0 ||
n%(i+128)==0 || n%(i+132)==0 || n%(i+138)==0 || n%(i+140)==0 || n%(i+146)==0 ||
n%(i+152)==0 || n%(i+156)==0 || n%(i+158)==0 || n%(i+162)==0 || n%(i+168)==0 ||
n%(i+170)==0 || n%(i+176)==0 || n%(i+180)==0 || n%(i+182)==0 || n%(i+186)==0 ||
n%(i+188)==0 || n%(i+198)==0)
return 0;
}
return 1;
}
시각:
$ time ./testprimebool.x 18446744065119617029 7
h(2,3,5,7)
Yes, its prime.
real 0m9.123s
user 0m9.132s
sys 0m0.000s
짝수 (막대 2)는 소수가 될 수 없다고 덧붙일 것입니다. 이로 인해 for 루프 전에 다른 조건이 발생합니다. 따라서 최종 코드는 다음과 같아야합니다.
int IsPrime(unsigned int number) {
if (number <= 1) return 0; // zero and one are not prime
if ((number > 2) && ((number % 2) == 0)) return 0; //no even number is prime number (bar 2)
unsigned int i;
for (i=2; i*i<=number; i++) {
if (number % i == 0) return 0;
}
return 1;
}
int is_prime(int val)
{
int div,square;
if (val==2) return TRUE; /* 2 is prime */
if ((val&1)==0) return FALSE; /* any other even number is not */
div=3;
square=9; /* 3*3 */
while (square<val)
{
if (val % div == 0) return FALSE; /* evenly divisible */
div+=2;
square=div*div;
}
if (square==val) return FALSE;
return TRUE;
}
Handling of 2 and even numbers are kept out of the main loop which only handles odd numbers divided by odd numbers. This is because an odd number modulo an even number will always give a non-zero answer which makes those tests redundant. Or, to put it another way, an odd number may be evenly divisible by another odd number but never by an even number (E*E=>E, E*O=>E, O*E=>E and O*O=>O).
A division/modulus is really costly on the x86 architecture although how costly varies (see http://gmplib.org/~tege/x86-timing.pdf). Multiplications on the other hand are quite cheap.
Using Sieve of Eratosthenes, computation is quite faster compare to "known-wide" prime numbers algorithm.
By using pseudocode from it's wiki (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), I be able to have the solution on C#.
public bool IsPrimeNumber(int val) {
// Using Sieve of Eratosthenes.
if (val < 2)
{
return false;
}
// Reserve place for val + 1 and set with true.
var mark = new bool[val + 1];
for(var i = 2; i <= val; i++)
{
mark[i] = true;
}
// Iterate from 2 ... sqrt(val).
for (var i = 2; i <= Math.Sqrt(val); i++)
{
if (mark[i])
{
// Cross out every i-th number in the places after i (all the multiples of i).
for (var j = (i * i); j <= val; j += i)
{
mark[j] = false;
}
}
}
return mark[val];
}
IsPrimeNumber(1000000000) takes 21s 758ms.
NOTE: Value might vary depend on hardware specifications.
Use for (i = 2; i <= number/i; i++) to limit iterations.
number%i, number/i is efficient on many compilers as the calculations of the quotient and remainder are done together, thus incurring no extra cost to do both vs. just 1.
A very simple solution:
bool IsPrime(unsigned number) {
for(unsigned i = 2; i <= number/i; i++){
if(number % i == 0){
return false;
}
}
return number >= 2;
}
참고URL : https://stackoverflow.com/questions/1538644/c-determine-if-a-number-is-prime
'programing tip' 카테고리의 다른 글
| 알림을 표시하지 않고 Foreground ()를 시작하는 방법은 무엇입니까? (0) | 2020.10.31 |
|---|---|
| 프로젝트의 / resources 폴더에있는 파일의 절대 경로를 얻는 방법 (0) | 2020.10.31 |
| 배열을 IEnumerable로 캐스팅 (0) | 2020.10.30 |
| Node.Js + Socket.IO 대 SignalR 대 C # WebSocket 서버 (0) | 2020.10.30 |
| IntelliJ : 로컬 및 git 커밋 / 브랜치간에 변경된 모든 파일의 차이점보기 (0) | 2020.10.30 |