#include "stdio.h"
#include "stdlib.h"
int prime(long int key){
    long int i=2;
    for(i=2;key%i!=0;i++);
    if(i==key)return 1;
    else return 0;
}
void main(){
    long int spn,i=2;
    printf("输入一个数,判断它是否两素数的乘积:\n");
    scanf("%ld",&spn);
    for(i=2;(i<spn)&&(!prime(i)||(spn%i)!=0||!prime(spn/i));i++);
    if(i==spn)printf("%ld不是两素数积",spn);    
    else printf("%ld=%ld*%ld",spn,i,spn/i);
}

还是很慢,其实速度也没提升什么哦,我测试了一个2345678,半天响应不了,昏

先做一个1000以内的素数表? 1000以内的素数可以直接用二分法查,超过1000就用这个表筛.
////////////////////////////
#include <iostream>
#include <cmath>

using namespace std;

void makeprimetable (int tab[], int n)
{
    int i, cnt;
    tab[0] = 2;

    for (i = 3, cnt = 1; cnt < n; i += 2) {
        int lim = (int)sqrt ((double)i);
        int j;
        for (j = 0; tab[j] <= lim && i % tab[j]; ++j);
        if (tab[j] > lim) {
            tab[cnt] = i;
            cnt++;
        }
    }            
}

bool binsearch (int tab[], int n, int num)
{
    int low = 0, high = n - 1, mid;

    while (low < high) {
        mid = (low + high)/2;
        if (num <= tab[mid])
            high = mid;
        else
            low = mid + 1;
    }
    return tab[low] == num;
}

int main ()
{
    const int n = 168;
    int tab[n];

    makeprimetable (tab, n);
    for (int i = 0; i < n; ++i)
        cout << tab[i] << ' ';
    cout << endl;
    cout << binsearch (tab, n, 997) << endl;
    return 0;
}

我一直还是理解 using namespace std是什么作用```大哥能解说一下吗?

这不是一类问题，而是做ACM题都要考虑的。看完问题后再看时/空限制，再看数据范围，然后再想怎么解。

测试数据n (2 =< n <=1000000);

这样的n如果非素数，则必存在一个素因子p,2<=p<1000，而n/p也在这个范围内，也可以筛出来。

素数表可以直接用数组保存，不用运行程序的时候算。

其实素数在整数里面是很少的，而且越往后越稀。

哦，谢了