算法基础之试除法判定质数

试除法判定质数

• 关键思路: 因为余数总是成对出现 所以 i <= n / i (i是一个余数 n/i是另一个)

  •   #include<iostream>
      using namespace std;
      bool is_prime(int x){
          if(x<2) return false;
          //i<=x/i 时间复杂度变成根号x
          for(int i=2;i<= x / i;i++){
              if( x % i == 0){
                  return false;
              }
          }
          return true;
      }
      int main(){
          int n;
          cin>>n;
          while(n--){
              int x;
              cin>>x;
              if(is_prime(x)) printf("Yes\n");
              else printf("No\n");
          }
      }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22