程序代码：

#include<stdio.h>

#define MAX 40001
char isPrime[MAX+1];
int prim[MAX+1];
int primSqre[MAX+1];

int main( void )
{
    int i=0;
    int j=0;
    int num=0;
    int data[2];
    
    scanf("%d",&data[0]);//输入一个数作为检查数据

    for (i=2;i<=MAX;++i)
    {
        if (!isPrime[i])
            prim[num++]=i;

        for (j=0;j<num&&i*prim[j]<=MAX;++j)
        {
            isPrime[i*prim[j]]=1;

            if (i%prim[j]==0)
                break;
        }
    }

    for (i=0;i<num;++i)
        primSqre[i]=prim[i]*prim[i];

    for (data[1]=data[0];;)
    {
        for (j=0;j<2;++j)
        {
            for (i=0;i!=num&&(data[j]%primSqre[i])&&primSqre[i]<=data[j];++i);
            
            if (i!=num&&primSqre[i]>data[j])
            {
                printf("%d\n",data[j]);
                                                    
                j=3;
            
                break;
             }        
          }
          
        if (j==3)
            break;
        
        if (data[0]>2)
            --data[0];           
        
         ++data[1]; 
    }

    return 0;
}