有没有能卡掉%6判断质数的办法
  • 板块灌水区
  • 楼主best_lover
  • 当前回复12
  • 已保存回复13
  • 发布时间2024/7/25 16:39
  • 上次更新2024/7/25 17:36:38
查看原帖
有没有能卡掉%6判断质数的办法
359485
best_lover楼主2024/7/25 16:39

RtRt,贴一手自己乱搞的题目(

发帖本意:hack 我这道题的 std (

在网上发现一个判断质数的办法(见下代码

if((n-1)%6==0)||(n-5)%6==0) {
    //n为质数
  }

发现能被卡掉以后,我~~(自作聪明)~~加了个特判(见下代码

if((((n-1)%6==0&&(n+5)/6)%5!=0)||((n-5)%6==0&&((n-5)/6)%5!=0)) {
    //n为质数
  }

以上面我的题目为例,有没有办法可以卡掉这种看起来就有点礼崩乐坏的做法(下附该题std。

#include<bits/stdc++.h>
using namespace std;
unsigned long long n,p[105],c[105],ans;
inline void divide(){
  if((((n-1)%6==0&&(n+5)/6)%5!=0)||((n-5)%6==0&&((n-5)/6)%5!=0)) {
    cout<<n-1;
    return;
  }
	int m=0;
	for(long long i=2;i*i<=n;i++){
		if(n%i==0) {
			p[++m]=i,c[m]=0;
			while(n%i==0) n/=i,c[m]++;
		}
	}
	if(n>1) p[++m]=n,c[m]=1;
	for(int i=1;i<=m;i++){
		ans+=(p[i]-1)*c[i];
	}
	cout<<ans;
}
int main(){
  // ios::sync_with_stdio(0);
  // cin.tie(0), cout.tie(0);
	cin>>n;
	divide();
  return 0;
}
2024/7/25 16:39
加载中...