那么我们就叫它是质数们的直接后代。现在，给你一系列自然数，判断它们是否是质数的直接后代，C语言

Question

问题：那么我们就叫它是质数们的直接后代。现在，给你一系列自然数，判断它们是否是质数的直接后代

#include<stdio.h>
int a[30];
int zhishu(int m)
{
    int i,t=0;
    if(m==2)
    return m;
    else
    {
    for(i=2;i<m;i++)
    {
        if(m!=i&&m%i==0)
        {
            t=1;
            return 0;
        }
    }
    }
    if(t==0)
    return m;
}
int main(){
     int m;
     scanf("%d",&m);
      int t,w;
     int i,j,k;
     for(k=0;k<m;k++)
     scanf("%d",&a[k]);
     for(k=0;k<m;k++)
     {
      t=0;
     for(i=2;i<a[k];i++)
     {
         if(zhishu(i))
         {
             if(a[k]%i==0)
         {
               w=a[k]/i;
               if(zhishu(w)&&i<=w)
               {
                   t=1;
                   printf("Yes\n");
               }
               
         }
         }
     }
          if(t==0)
    
{
      printf("No\n");
}
    }
  return 0;
}

这个程序怎么才能降低时间复杂度啊

Answer 1

工作室课题—质数的后代_淡灰灰灰的博客-CSDN博客 质数的后代Description在上一季里，曾提到过质数的孤独，其实从另一个角度看，无情隔膜它们的合数全是质数的后代，因为合数可以由质数相乘结合而得。如果一个合数由两个质数相乘而得，那么我们就叫它是质数们的直接后代。现在，给你一系列自然数，判断它们是否是质数的直接后代。Input第一行一个正整数T，表示需要判断的自然数数量接下来T行，每行一个要判断的自然数Output共T行，依次对于输入中给出的自然数，判断是否为质数的直接后代，是则输出Yes，否则输出NoSa_质数的后代 https://blog.csdn.net/weixin_51717063/article/details/123761103