A
输出每个比幸运数字大的最小素数
#include
#include
#include
using namespace std;
const int Max=1e6+100;
bool a[Max]={0};
int T,N,n;
void prime(){ //打出素数表
for(int i=2;i<Max;i++){
int k=1;
for(int j=2;j*j<=i;j++){
if(i%j==0){k=0;break;}
}
if(k)a[i]=1; //如果是素数·标记其对应下标
}
}
int main(){
cin>>T;
prime();
int tail=1;
while(T--){
cin>>N;
long long sum=0;
for(int i=0;i<N;i++){
cin>>n;
for(int j=n+1;j<Max;j++){ //从n+1开始遍历输出第一个素数
if(a[j]==1){sum+=j;break;}
}
}
printf("Case %d: %lld Xukha\n",tail,sum);
tail++;
}
return 0;
}C
偶数都可以是两个素数的和，输出该数可以有多少种两素数和的情况
#include
#include
using namespace std;
const int Max=1e7+10;
int T,N;
int a[700000],tail=0; //刚开始a[Max],老是runtime error.
bool b[Max];
void prime(){ //打印素数表，线性筛
memset(b,1,sizeof(b));
b[0]=b[1]=0;
for(int i=2;i<Max;i++){
if(b[i]){
a[tail++]=i; //a[]储存素数
}
for(int j=2*i;j<Max;j+=i){
b[j]=0; //对于每个合数对其标记
}
}
}
int main(){
prime();
scanf("%d",&T);
int ta=1;
while(T--){
scanf("%d",&N);
int sum1=0;
for(int i=0;a[i]<=N/2;i++){ //遍历每个素数，如果N-该素数是素数，情况加一
if(b[N-a[i]]) sum1++;
}
printf("Case %d: %d\n",ta++,sum1);
}
return 0;
}D
找出小于该数两个数（a,b）的最小公倍数等于该数的所有情况和且（a<=b）
n=p1^a1 * p2^a2 * p3^a3 * p4^a4...* pn^an (p为素数）
a=p1^b1 * p2^b2 * p3^b3 * p4^b4...* pn^bn (p为素数）
b=p1^c1 * p2^c2 * p3^c3 * p4^c4...* pn^cn (p为素数）
n=icm(a,b)=p1^max(b1,c1) * p2^max(b2,c2) * p3^max(b3,c3)
即,a1=max(b1,c1),a2=max(b2,c2),a3=max(b3,c3)对于a,b至少一个因子指数与n的相等
(n=8
n=2^3
(2^0,2^3),(2^1,2^3),(2^2,2^3),(2^3,2^3),(2^3,2^0),(2^3,2^1),(2^3,2^2)
一共有2*an+1种情况
由于a<b,最后需加一除二
)
#include
#include
#include
#include
using namespace std;
const int Max=1e7+10;
int T,a[Max/10],tail=0;
bool b[Max];
long long N;
void icm(){ //线性筛，打印素数表
memset(b,1,sizeof(b));
for(int i=2;i<Max;i++){
if(b[i]){
a[tail++]=i;
for(int j=2*i;j<Max;j+=i){
b[j]=0;
}
}
}
}
int main(){
icm();
cin>>T;
for(int ta=1;ta<=T;ta++){
cin>>N;
long long sum1=1;
for(int i=0;i<tail && a[i]<=N;i++){ //质因数分解
int p=0;
while(N%a[i]==0){
p++;
N=N/a[i];
}
sum1*=(2*p+1); //p为n质因子的指数
}
if(N!=1)sum1*=3; //素数表只打印到![图片说明]，对于较大的素数另行判断(https://www.nowcoder.com/equation?tex=%5Csqrt%7Bn%7D "图片标题")
sum1=(sum1+1)/2;
printf("Case %d: %lld\n",ta,sum1);
}
return 0;
}E
x=a^b(根据x求b)
求x所有质因子指数的最大公约数
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int Max=1e5+10;
int K,k,s,sym;
long long N;
int a[Max/10],tail=0;
int gcd(int x,int y){ //求最大公约数
int t;
if(x<y){t=x;x=y;y=t;}
while(x%y!=0){
t=x%y;
x=y;
y=t;
}
return y;
}
void icm(){ //打印素数表
for(int i=2;i<Max;i++){
bool f=1;
for(int j=2;j*j<=i;j++){
if(i%j==0){f=0;break;}
}
if(f)a[tail++]=i;
}
}
int main(){
icm();
cin>>K;
for(int ta=1;ta<=K;ta++){
sym=1;
cin>>N;
int ff=1,su;
if(N<0){N=-N;sym=-1;} //存在负数，先取正，如果是负数·结果只能是奇数
for(int i=0;i<tail&&a[i]<=N;i++){
s=0;
while(N%a[i]==0){
N=N/a[i];
s++; //质因子指数的个数
}
if(ff&&s){su=s;ff=0;continue;}
if(s)su=gcd(s,su); //求所有指数的最大公约数
}
printf("Case %d: ",ta);
if(N==1){
if(sym==-1){while(su%2==0)su=su/2;} //如果是负数，除二的奇数
cout<<su<<endl;
}
else cout<<"1\n"; //如果N是素数输出一
}
return 0;
}F
大数取模，判断余数是否为零
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
short int T;
long long b,x,y;
string a,s;
int main(){
cin>>T;
for(int ta=1;ta<=T;ta++){
cin>>a>>b;
if(a[0]=='-')a[0]='0';
if(b<0)b=-b; //负数取正，不影响结果
int len=a.size();
x=a[0]-'0';
//cout<<x<<endl;
//cout<<a<<" "<<b<<" "<<len<<" ";
for(int i=1;i<len;i++){
x=(x*10+(a[i]-'0'))%b; //取模
}
x=x%b;
//cout<<x<<endl;
printf("Case %d: ",ta);
if(x==0)cout<<"divisible\n";
else cout<<"not divisible\n";
}
return 0;
}G
计算[a,b]区间素数的个数
排除掉[a,b]内合数，计算b^0.5内的素数的倍数从而排除[a,b]内合数
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int Max=1e5/2;
long long a,b,A;
int T;
int x[Max],tail=0;
bool y[100010];
void prim(){ //线性筛
for(int i=2;i<Max;i++){
bool f=1;
for(int j=2;j*j<=i;j++){
if(i%j==0){f=0;break;}
}
if(f)x[tail++]=i;
}
}
int main(){
prim();
cin>>T;
for(int ta=1;ta<=T;ta++){
cin>>a>>b;
memset(y,0,sizeof(y));
for(int i=0;i<tail && x[i]<=b;i++){
A=a/x[i];
if(A<2)A=2; //素数的倍数为合数（最小为2）
for(long long j=x[i]*A;j<=b;j+=x[i]){
if(j-a>=0){y[j-a]=1;} //排除[a,b]区间内合数
}
}
int _sum=0;
for(int i=a;i<=b;i++){
if(!y[i-a])_sum+=1; //计算[a,b]内非合数的个数
}
if(a==1)_sum--; //1不是素数
printf("Case %d: %d\n",ta,_sum);
}
return 0;
}
J
计算该行数任意两个数的最大公约数的最大值
python的input()为行输入，暴力枚举求最大公约数
T=int(input())
for i in range(T):
a=list(map(int,input().split())) //行输入数组
l=len(a)
a=list(sorted(a))
max1=0
for j in range(l-1):
for k in range(j+1,l):
x=a[j]
y=a[k]
while(x%y!=0): //求最大公约数
t=x%y
x=y
y=t
max1=max(max1,y)
print(max1)H
判断是否为素数
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int N,tail=1;
int main(){
while(cin>>N){
int k=1;
if(N<=0)break;
if(N==1 || N==2) k=0;
else{
for(int i=2;i*i<=N;i++){
if(N%i==0){k=0;break;}
}
}
printf("%d: ",tail);
if(k)cout<<"yes\n";
else cout<<"no\n";
tail++;
}
return 0;
}
京公网安备 11010502036488号