本文主要是介绍【SGU】113. Nearly prime numbers 合数分解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
传送门:【SGU】113. Nearly prime numbers
题目分析:O(sqrt(N))。。
代码如下:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std ;#define rep( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i )
#define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 5 ;int n ;bool check ( int x ) {int top = 0 ;for ( int i = 2 ; i * i <= x ; ++ i ) {if ( x % i == 0 ) {while ( x % i == 0 ) {x /= i ;top ++ ;if ( top > 2 ) return 0 ;}}}if ( x > 1 ) ++ top ;return top == 2 ;
}void solve () {int x ;For ( i , 1 , n ) {scanf ( "%d" , &x ) ;printf ( check ( x ) ? "Yes\n" : "No\n" ) ;}
}int main () {while ( ~scanf ( "%d" , &n ) ) solve () ;return 0 ;
}
这篇关于【SGU】113. Nearly prime numbers 合数分解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!