来源于@Hywhh

数学
来源于@Hywhh

用户头像
一只数竞牛马 更新于2022-11-2 06:48:13

一个数质因数分解,其最大质因子末位加一个与该最大质因子末位相同的数,如13变成133。

循环此过程,最终必是一个质数。若存在a 使得对任意大于2的正整数进行a次循环后必定得到质数 求此a的最小值 若不存在,说明理由

有问必答
有问必答
收起
2
分享
共7条回复
时间正序
用户头像
Hywhh
1月前
前排滋滋
用户头像
soul
1月前

快去早读jj-huaji

1条评论
用户头像
一只数竞牛马
1月前

jj-chengbikong笑死了

用户头像
质心儿子
1月前

看到此题,初步认为不存在a,即$a \to \infty$。

下面的程序输入a,输出最小的进行a次操作后得到质数的数。

#include <cstdio>
#include <cmath>
#pragma GCC optimize('Ofast')

int max(int a,int b) {
	return a>b?a:b;
}

bool prime(int n) { //判断n是否为质数 
	if (n == 2 || n == 3) return true;
	if (n % 6 == 1 || n % 6 == 5) {
		for (register int i=2;i<ceil(sqrt(n));++i)
			if (n % i == 0) return false;
		return true;
	} else return false;
}

inline int Maxprime(int n,int t=2) { //求n的不比t小的最大质因子
	if (prime(n)) return n;
	for (int i=t;i<=floor(sqrt(n));++i) {
		if (n % i == 0) if (prime(i)) {
			return max(i,Maxprime(n/i,i));
		} 
	} return 2;
}

inline int play(int n,int s=0) {
	if (prime(n)) {
		return s;
	} else {
		int m=Maxprime(n);
		return play(m*10+m%10,s+1);
	}
}

signed main() {
	int a=1;
	while (a>0) {
		scanf("%d",&a);
		for (register int i=2;;++i) {
			if (play(i) == a) {
				printf("%d\n",i);
				break;
			}
		}
	} return 0;
} 

运行。

image.png

从a=1算到a=19,前面都是秒出答案,注意这里a=5算出4是没有问题的,操作过程4->22->111->377->299->233。a=16卡了2秒算出669454,a=17卡了十几秒算出2059306,a=18……大概1分钟吧,算出9290338。a=19可是算了7-8分钟,终于算出16831162。后面不想算了,再大一点就要算很久。不过虽然要算很久,看这个趋势,应该都是可以算得出来的,不至于没有结果。可以认为对于$\forall a \exist p \in R \ni p$进行$a$次操作后得到质数。

4条评论
用户头像
质心儿子
1月前

有一个小错误,第12行的<ceil应为<=floor,不过问题不大,因为刚好算出完全平方数的概率很小。

用户头像
质心儿子 回复 质心儿子
1月前

不对呀,我20行就用的floor,为什么12行用了ceil?

用户头像
一只数竞牛马
1月前

a=3是50?50-55-111-377-299-233 5次操作啊

用户头像
质心儿子 回复 一只数竞牛马
1月前

看来问题还是有点大。

用户头像
质心儿子
1月前

不过为什么刚刚上传图片的时候forum.eduzhixin.com显示“色情”?

image.png

2条评论
用户头像
一只数竞牛马
1月前

jj-chengbikong现在真的小网站都叫正能量网站了 

用户头像
soul 回复 一只数竞牛马
1月前

你不对劲jj-huaji

用户头像
质心儿子
1月前

将第12行的<ceil改为<=floor之后,得到了新的答案。

image.png

与原来答案大体相同,但a=3时得到了74,而非50。

4条评论
用户头像
一只数竞牛马
1月前

这很可以 虽然本意是数论题。。谢佬

用户头像
质心儿子 回复 一只数竞牛马
1月前

主要是我不懂数论。

用户头像
质心儿子 回复 一只数竞牛马
1月前

而且我对质数的认识仅仅停留于O(sqrt n)。

用户头像
一只数竞牛马
1月前

已经很强了佬jj-huaji

用户头像
质心儿子
1月前

大概算了90分钟吧,a=20的结果是112745722。

5条评论
用户头像
soul
1月前

数学题计算机解法了属于是zx-caizixing2@2x

用户头像
soul
1月前

羡慕你们会计算机啊!zx-zhaopeng1@2x

用户头像
回复 soul
1月前

别羡慕,我后悔学计算机了zx-tangpeng1@2x

用户头像
soul 回复
1月前

西卡西,我现在想后悔都迟了zx-caizixing2@2x

用户头像
soul 回复
1月前

为啥后悔捏,不是挺好的吗(都说物竞生得会计算机)

用户头像
1月前
不过楼主@质心儿子 掌握c++要比我多很多,膜一下
2条评论
用户头像
质心儿子
1月前

不要以为你是质心学员就可以乱夸蒟蒻,不要以为你可以点赞就乱点,你没有理由!虽然在质心,学员享有最高体验,你认为我强的,你就赞吧,你甚至可以模我。但是,群众的眼睛是雪亮的!如果你赞了我,我会让全天下物竞生都知道,质心学员的腐朽!质心将会臭名昭著!

(上述内容改编自某个不知名的地方)

用户头像
回复 质心儿子
1月前

。。。