c语言编程题目 整数n=p*q，p和q为质数，且p≠q，我们称n为D-Prime，请写个程序判断一个数是不是D_Prime。

c语言编程题目 整数n=p*q，p和q为质数，且p≠q，我们称n为D-Prime，请写个程序判断一个数是不是D_Prime。

您好，我把之前的code优化了下，加入了素数数组，保存之前，计算过程中，发现的素数，并且在查找时，用了二分查找。你试试看是否还会超时吧。
（在codeblock下测试过，没有问题）
#include
#include
#define N 100000  //sqrt(NMAX)
#define NMAX 100000000

int binary_search(int src[], int num,int tar){//二分查找
int head = 0;
int tail = num - 1;
int mid;
while(head < tail){
mid = (head + tail) / 2;
if(src[mid] == tar){
return 1;
}else if(src[mid] < tar){
head = mid + 1;
}else
tail = mid - 1;
}
if(src[head] == tar){
return 1;
}
return 0;
}
int is_prime(int tar, int *prime_lib, int *next_idx){//判断是否为素数
if(tar < prime_lib[*next_idx - 1]){
if(binary_search(prime_lib, *next_idx, tar) == 1)
return 1;
else
return 0;
}
    int i = 1;
int tmp_end = sqrt((float)tar);
    while(i < *next_idx && prime_lib[i]<= tmp_end){//只考虑素数数组里的
        if(tar % prime_lib[i] == 0)
            return 0;
        i++;
    }
if(i == *next_idx){//大于素数最大时，依次增加1
int cur_val = prime_lib[*next_idx - 1] + 1;
while(cur_val <= tmp_end){
if(is_prime(cur_val,prime_lib, next_idx)){
prime_lib[(*next_idx)++] = cur_val;
if(tar % cur_val == 0)
return 0;
}
cur_val++;
}
}
    
    return 1;
}
int main(){
int prime_lib[N]; //保存之前过程中找到的素数，按大小顺序保存
prime_lib[0] = 1;
prime_lib[1] = 2;
int next_value = 2;
int *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
");
                flag = 1;
                break;
            }
        }
        if(!flag)
            printf("NO
");
    }
    return 0;
}追问太复杂了。表示有点看不懂啊！还有素数和1也是的，素数和1 不是不是的吗？望指教，尽量简洁好懂一点，谢谢，帮帮忙吧！来自：求助得到的回答

#include 

int prime(int n)
{
    int i;

    for (i = 2; i * i <= n; i++)
        if (n % i == 0)
            return 0;
    return 1;
}

int foo(int n)
{
    int i;

    for (i = 2; i * i < n; i++)
        if (n % i == 0 && prime(i) && prime (n / i))
            return 1;
    return 0;
}

int main(void)
{
    int k, n;

    scanf("%d", &k);

    while (k--) {
        scanf("%d", &n);

        if (foo(n))
            printf("yes ");
        else
            printf("no ");

    }

    return 0;
}追问不好意思，错了。可不可以优化点啊！
Acceteped : 254 Submit : 1037Time Limit : 2000 MS
Memory Limit : 65536 KB
你的那个1，2,3，不能过啊！他们不是吧！望指教，谢谢