練習問題/回答例

素数判定

  1. #include <iostream>
  2. #include <cmath>
  3. #include <sstream>
  4.  
  5. using namespace std;
  6. int main( int argc, char** argv ){
  7. int x;
  8. bool is_prime = true;
  9.  
  10. if(argc < 2){
  11. cout << "Input x > ";
  12. cin >> x;
  13. }else{
  14. istringstream is(argv[1]);
  15. is >> x;
  16. }
  17.  
  18. for( int i = 2; i < static_cast<int>(sqrt(x)) + 1; i++){
  19. if(( x % i ) == 0 ){
  20. is_prime = false;
  21. break;
  22. }
  23. }
  24.  
  25. if( is_prime )
  26. cout << x << "は素数" << endl;
  27. else
  28. cout << x << "は非素数" << endl;
  29. return 0;
  30. }

素数列挙

vectorを使って

  1. #include <iostream>
  2. #include <sstream>
  3. #include <vector>
  4. using namespace std;
  5. int main( int argc, char** argv ){
  6. vector<bool> prime;
  7. int x;
  8.  
  9. if(argc < 2){
  10. cout << "Input x > ";
  11. cin >> x;
  12. }else{
  13. istringstream is(argv[1]);
  14. is >> x;
  15. }
  16.  
  17. // 初期化
  18. for(int i=0; i <= x; i++)
  19. prime.push_back(true);
  20.  
  21. // 0と1は外す
  22. prime[0] = prime[1] = false;
  23.  
  24. // 倍数をふるい落とす
  25. for(int i=2; i <= x; i++){
  26. if(prime[i]) {
  27. for(int j=2; j*i <= x; j++)
  28. prime[i*j] = false;
  29. }
  30. }
  31.  
  32. // 残ったものを表示
  33. for(int i=0; i <= x; i++)
  34. if(prime[i])
  35. cout << i << endl;
  36. return 0;
  37. }