C(clang 3.9) 解法, 执行用时: 19ms, 内存消耗: 416K, 提交时间: 2020-07-10 23:31:35

#include <stdio.h>
int n, m, i, j, k, c, s[100005];
int main(){
	scanf("%d", &m);
	while(m--){
		scanf("%d", &n);
		for(k=n, c=0, i=2; i*i<=n; i++){
			if(n%i == 0) s[++c] = i;
			while(n%i == 0) n /= i;
		}
		if(n > 1) s[++c] = n;
		if(s[c] == k) printf("isprime\n");
		else printf("noprime\n");
		for(i=1; i<c; i++){
			printf("%d ", s[i]);
		}
		printf("%d\n", s[i]);
	}
	return 0;
}

C++(clang++11) 解法, 执行用时: 17ms, 内存消耗: 404K, 提交时间: 2020-10-28 09:29:02

#include<bits/stdc++.h>
using namespace std;
int t,x,i;
int main(){
	for(scanf("%d",&t);t;t--){
		scanf("%d",&x);
		for(i=2;i*i<=x;i++)
			if(x%i==0)break;
		if(i*i>x)puts("isprime");
		else puts("noprime");
		for(;i*i<=x;i++){
			if(x%i)continue;
			while(x%i==0)x/=i;
			printf("%d ",i);
		}
		if(x>1)printf("%d",x);
		puts("");
	}
	return 0;
}

Python3 解法, 执行用时: 1000ms, 内存消耗: 4752K, 提交时间: 2022-03-28 18:32:18

for _ in range(int(input())):
	n=int(input())
	p,f=2,1
	#唯一基本定理
	while p*p<=n:
		if n%p==0:
			if f:
				print("noprime")
				f=0
			print(p,end=" ")
			while n%p==0:
				n//=p
			#通过筛出完，最后由于唯一基本定理，合数一定是有不同质数的幂次相乘而成
				#变式埃氏筛
				
		p+=1
		#循环退出的终止条件
	if f:print("isprime")
	if n>1:print(n,end=" ")
	print()
	#每一个式子循环结