题解 1485: 蓝桥杯算法提高VIP-Torry的困惑(提高型)

来看看其他人写的题解吧!要先自己动手做才会有提高哦! 
返回题目 | 我来写题解

筛选

高效素数判断方法以及取模公式

解题思路:本体采用的取模公式为a*b%c=((a%c)*(b%c))%c,求前n个质数的积对于50000的模,就相当于每一次与质数相乘后对于50000取模,然后再与下一个质数相乘,再取模,相乘取模的步骤替换为上述公式右边的步骤,这样简化了计算过程的复杂度,

python不超时解法

解题思路:为了不超时,需要优化素数判断方法除此之外,在循环乘时判断依据不应该用n自减,加个计数变量与n比大小,用n自减会超时80左右注意事项:参考代码:frommathimportsqrtdefjudge(i):#优化后的素数判断方法ifi%2==0:returni==2ifi%3==0:return

蓝桥杯算法提高VIP-Torry的困惑(提高型) -(Python代码)

解题思路:解决此题的关键就是筛选质数和大数乘取模的方法,普通的筛法无疑是会超时的,现存高效的质数筛选方法有埃氏筛、线性筛等,理论来说线性筛更高效,考虑数据规模并不太大,本题使用埃氏筛来进行质数的筛选,筛法具体的思想就不在此赘述,有兴趣的题友可以自行搜索素数筛;然后再来说说大数乘取模,

C++解Torry的困惑(提高型)

摘要:解题思路:从3开始逐个寻找质数并相乘,直到质数的个数等于n。实现的具体代码有详细备注注意事项:参考代码:#include<iostream>#include<cmath>#include<vector……

时间超限解决方案

摘要:解题思路:相信大部分人卡在了时间超限这儿,实际上就是判断质数时的比较次数太多了,如下给出解决注意事项:参考代码:#include<stdio.h>int judge(int n){ int a=1; ……