소수구하기(C++)

1000이하의 n을 입력 받아서 n이하의 모든 소수를 구해서 출력하라. 출력은 공백 한칸을 두고 한줄에 10개씩 하여라.

#include <iostream>
#include <windows.h>

using namespace std;
int main(){
   
    int n, i, j, k=0;
    bool sosu;
   
   
    cin >> n;
   
    for(i=2;i<=n;i++){//소수는 양의약수를 2개만 가지고 있는 1보다 큰 자연수이다. 따라서 1은 포함할 필요가 없다.
                     sosu=true;
                     for(j=2;j<i;j++){
                                      if(i%j==0){
                                                 sosu=false;
                                                 break;
                                      }
                     }
                     if(sosu){
                              cout<<i<<" ";
                              k++;
                     }
                     if(k==10){
                               cout<<endl;
                               k=0;
                     }
    }
   
    system("PAUSE");
   
    return 0;
}


실행결과
100
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 Press any key to continue . . .

                                        


하지만 이보다 효율적인 방법이 있었다,,,,


n이 소수가 아니라면 n은 두개의 1보다 큰 자연수의 곱으로 나타낼수 있다.
n= a x b 
따라서, a와 b중 하나는  √n  이하일 수 밖에 없기 때문에 2부터 √n  까지만 나눠보면 된다.


#include <iostream>
#include <cmath>
#include <windows.h>
using namespace std;

int main(){
   
    int n,i,j,k=0;
    bool sosu;
       
    cin>>n;
   
    for(i=2;i<=n;i++){
                      sosu = true;
                      for(j=2;j<=sqrt(i);j++){//sqrt는 <cmath>의 함수이다.
                                              if(i%j==0){
                                                         sosu = false;
                                                         break;
                                              }
                      }
                      if(sosu){
                               cout << i <<" ";
                               k++;
                      }
                     
                      if(k==10){
                                cout << endl;
                                k=0;
                      }
    }
   
    system("PAUSE");
   
    return 0;
}

 실행결과

1000
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349
353 359 367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457 461 463
467 479 487 491 499 503 509 521 523 541
547 557 563 569 571 577 587 593 599 601
607 613 617 619 631 641 643 647 653 659
661 673 677 683 691 701 709 719 727 733
739 743 751 757 761 769 773 787 797 809
811 821 823 827 829 839 853 857 859 863
877 881 883 887 907 911 919 929 937 941
947 953 967 971 977 983 991 997 Press any key to continue . . .

여기서 더 계산과정을 효울적으로 바꿀수 있다.

2부터 √n 까지 모든 자연수를 나누지 말고, 그중에서도 소수만 나누는 방법이다.

어떤 자연수가 합성수라는 것은 그 자연수는 자신보다 작은 어떤 소수들의 곱이라는 것이다. 게다가 앞에서 말했듯이 그 소수들 중 하나는 적어도 √n  이하이다.

따라서, n을 나누어 떨어뜨리는√n  이하인 소수가 존재한다면, n은 소수가 아니다.

그렇다면, 어떻게 하면 소수 들만 나눠볼수 있을까. 나눌때 소수인지 판정한 다음 나누는 건 오히려 더 비효율 적이다.

문제에서 1000이하의 입력값을 제시하였으므로 배열을 만들어 순차적으로 소수들을 저장해가며 배열에 저장된 값으로 나눠보는 방법을 사용할 수 있겠다.


#include <iostream>
#include <cmath>
#include <windows.h>
using namespace std;

int main(){
   
    int n,i,j,k=0,p=1,a[1000];
    bool sosu;
       
    cin>>n;
   
    a[0]=2;
       
    for(i=2;i<=n;i++){
                      sosu = true;
                      for(j=0;a[j]<=sqrt(i);j++){

/*여기서 한가지 전제를 한다:임의의 자연수 n에 대해 n보다 작고 √n  보다큰 소수가 항상 존재한다. 그렇지 않다면, a[j]는 쓰래기 값을 받을 것이다.*/

                                              if(i%a[j]==0){
                                                         sosu = false;
                                                         break;
                                              }
                      }
                      if(sosu){
                               cout << i <<" ";
                               a[p++]=i;
                               k++;
                      }
                     
                      if(k==10){
                                cout << endl;
                                k=0;
                      }
    }
   
    system("PAUSE");
   
    return 0;
}

실행결과


2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349
353 359 367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457 461 463
467 479 487 491 499 503 509 521 523 541
547 557 563 569 571 577 587 593 599 601
607 613 617 619 631 641 643 647 653 659
661 673 677 683 691 701 709 719 727 733
739 743 751 757 761 769 773 787 797 809
811 821 823 827 829 839 853 857 859 863
877 881 883 887 907 911 919 929 937 941
947 953 967 971 977 983 991 997 Press any key to continue . . .