c语言编程题目 整数n=p*q,p和q为质数,且p≠q,我们称n为D-Prime,请写个程序判断一个数是不是D_Prime.输入第一行是一个整数K,表示样例的个数.以后每行是一个整数x,(1 ≤ x ≤ 100,000,000);输出每行输

c语言编程题目 整数n=p*q,p和q为质数,且p≠q,我们称n为D-Prime,请写个程序判断一个数是不是D_Prime.输入第一行是一个整数K,表示样例的个数.以后每行是一个整数x,(1 ≤ x ≤ 100,000,000);输出每行输
c语言编程题目 整数n=p*q,p和q为质数,且p≠q,我们称n为D-Prime,请写个程序判断一个数是不是D_Prime.
输入
第一行是一个整数K,表示样例的个数.以后每行是一个整数x,(1 ≤ x ≤ 100,000,000);
输出
每行输出一个样例的结果,如果是输出“Yes”,否则输出“No”.
样例输入
4 30 121 21 12
样例输出
No No Yes No不好意思,那个超时啦!在优化一点吧!

c语言编程题目 整数n=p*q,p和q为质数,且p≠q,我们称n为D-Prime,请写个程序判断一个数是不是D_Prime.输入第一行是一个整数K,表示样例的个数.以后每行是一个整数x,(1 ≤ x ≤ 100,000,000);输出每行输

您好,我把之前的code优化了下,加入了素数数组,保存之前,计算过程中,发现的素数,并且在查找时,用了二分查找.你试试看是否还会超时吧.

（在codeblock下测试过,没有问题）

#include<stdio.h>
#include<math.h>
#define N 100000  //sqrt(NMAX)
#define NMAX 100000000

int binary_search(int src[], int num,int tar){//二分查找
\x09int head = 0;
\x09int tail = num - 1;
\x09int mid;
\x09while(head < tail){
\x09\x09mid = (head + tail) / 2;
\x09\x09if(src[mid] == tar){
\x09\x09\x09return 1;
\x09\x09}else if(src[mid] < tar){
\x09\x09\x09head = mid + 1;
\x09\x09}else
\x09\x09\x09tail = mid - 1;
\x09}
\x09if(src[head] == tar){
\x09\x09return 1;
\x09}
\x09return 0;
}
int is_prime(int tar, int *prime_lib, int *next_idx){//判断是否为素数
\x09if(tar < prime_lib[*next_idx - 1]){
\x09\x09if(binary_search(prime_lib, *next_idx, tar) == 1)
\x09\x09\x09return 1;
\x09\x09else
\x09\x09\x09return 0;
\x09}
    int i = 1;
\x09int tmp_end = sqrt((float)tar);
    while(i < *next_idx && prime_lib[i]<= tmp_end){//只考虑素数数组里的
        if(tar % prime_lib[i] == 0)
            return 0;
        i++;
    }
\x09if(i == *next_idx){//大于素数最大时,依次增加1
\x09\x09int cur_val = prime_lib[*next_idx - 1] + 1;
\x09\x09while(cur_val <= tmp_end){
\x09\x09\x09if(is_prime(cur_val,prime_lib, next_idx)){
\x09\x09\x09\x09prime_lib[(*next_idx)++] = cur_val;
\x09\x09\x09\x09if(tar % cur_val == 0)
\x09\x09\x09\x09\x09return 0;
\x09\x09\x09}
\x09\x09\x09cur_val++;
\x09\x09}
\x09}
    
    return 1;
}
int main(){
\x09int prime_lib[N]; //保存之前过程中找到的素数,按大小顺序保存
\x09prime_lib[0] = 1;
\x09prime_lib[1] = 2;
\x09int next_value = 2;
\x09int *next_idx = &next_value;
    int num, i, j;
    scanf("%d", &num);
    for(i = 0; i < num; i++){
        int cur_val;
        scanf("%d", &cur_val);
        int flag = 0; //标记
        for(j = 1; j<= sqrt((float)cur_val); j++){//这里也有优化
            if(cur_val % j ==0&&j!=cur_val/j&&is_prime(j,prime_lib, next_idx) && is_prime(cur_val / j, prime_lib, next_idx)){
            //这里的if条件就是判断当前的元素,是否满足条件
            //1.从左往右,依次判断cur_val是否能整除j
            //2.如果1.满足,则看j和cur_val/j是否相等,相等,不满足题意
            //3.如果2满足,则判断j是否是质数
            //4.如果3满足,则判断cur_val/j是否是质数
            //如果4满足则说明这个数,满足题意了.
                printf("YES\n");
                flag = 1;
                break;
            }
        }
        if(!flag)
            printf("NO\n");
    }
    return 0;
}