[解题报告]《算法零基础100讲》(第7讲) 素数判定
2021/12/26 17:07:48
本文主要是介绍[解题报告]《算法零基础100讲》(第7讲) 素数判定,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 一、回文素数
- 题目描述
- 思路分析
- 具体代码
- 二、丑数
- 题目描述
- 思路分析
- 具体代码
一、回文素数
力扣:866.回文素数
题目描述
求出大于或等于 N 的最小回文素数。
回顾一下,如果一个数大于 1,且其因数只有 1 和它自身,那么这个数是素数。
例如,2,3,5,7,11 以及 13 是素数。
回顾一下,如果一个数从左往右读与从右往左读是一样的,那么这个数是回文数。
例如,12321 是回文数。
思路分析
从n开始分别判断n是否是回文素数,同时注意不存在长度为8的素数,直接跳过即可。
具体代码
class Solution { public: int reverse(int n){ int ans=0; while(n){ ans=ans*10+n%10; n/=10; } return ans; } bool isPrime(int n){ if(n==1) return false; for(int i=2;i<=sqrt(n);i++){ if(n%i==0){ return false; } } return true; } int primePalindrome(int n) { while(1){ if(n==reverse(n) && isPrime(n)){ return n; } n++; if (10000000 < n && n < 100000000) n = 100000000; } } };
二、丑数
力扣:剑指 Offer 49. 丑数
题目描述
我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。
思路分析
丑数只包含质因子2、3、5,所以对于一个丑数来说,它一定是一个丑数乘以2或者3或者5.我们可以设置三个指针分别指向乘以2、3、5,我们取其中最小的数保存到对应的dp [i] 中,dp[i] 表示:第i个丑数。注意1是第一个丑数,我们从前循环遍历到n即可。
具体代码
class Solution { public: int dp[1692]; int nthUglyNumber(int n) { dp[1]=1; int p2=1,p3=1,p5=1; for(int i=2;i<=n;i++){ dp[i]=min(dp[p2]*2,min(dp[p3]*3,dp[p5]*5)); if(dp[i]==dp[p2]*2){ p2++; } if(dp[i]==dp[p3]*3){ p3++; } if(dp[i]==dp[p5]*5){ p5++; } } return dp[n]; } };
这篇关于[解题报告]《算法零基础100讲》(第7讲) 素数判定的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)