fft质数打表程序

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void foo(ll x){
	int flag=0;
	for(ll i=2;i*i<=x;++i)
		if(x%i==0){
			int j=0;
			for(;x%i==0;x/=i)
				++j;
			if(flag++)
				cout<<"*";
			cout<<i;
			if(j!=1)
				cout<<"^"<<j;
		}
	if(x!=1){
		if(flag)
			cout<<"*";
		cout<<x;
	}
	cout<<endl;
}
bool bar(ll x){
	for(ll i=2;i*i<=x;++i)
		if(x%i==0)
			return 0;
	return 1;
}
ll pow(ll u,ll v,ll p){
	ll a=1;
	for(;v;v>>=1){
		if(v&1)
			a=a*u%p;
		u=u*u%p;
	}
	return a;
}
ll root(ll d,ll q){
	ll k=0,a[16];
	for(ll i=2,j=d;;++i){
		if(j%i==0){
			a[k++]=i;
			while(j%i==0)
				j/=i;
		}
		if(j<i*i){
			if(j!=1)
				a[k++]=j;
			break;
		}
	}
	for(ll i=2;;++i){
		ll j=0;
		for(;j!=k&&pow(i,
		d/a[j],q)!=1;++j);
		if(j==k)
			return i;
	}
}
int m;ll x,v[10000];
int main(){
	for(int j=17;j<30;++j)
		for(ll i=1;
		(x=i*(1<<j)+1)<1e8;++i)
			if(i%2&&bar(x))
				v[m++]=x;
	sort(v,v+m);
	for(int i=0;i!=m;++i){
		cout<<setw(8)<<v[i]
		<<setw(4)
		<<root(v[i]-1,v[i]);
		int j=0;
		for(--v[i];v[i]%2==0;++j)
			v[i]/=2;
		cout<<setw(4)<<"2^"
		<<j<<" * "
		<<setw(5)<<v[i]<<endl;
	}
}