(C/C++学习) 37. 关于力扣204. 计数质数的相关推导
2021-05-13 09:30
阅读：395
标签：问题 一个 c++学习 假设 计数 学习 开始 大于 c++ 前言： 本文主要记录关于力扣 （204. 计数质数问题）的两个问题推导： 1. 对于任意一个大于 2 的正整数 n, 如果在区间 [2, √n] 之间不存在 n 的正整数乘法因子 a , 那么 n 是质数。 推导：在上述前提下，假设在 (√n, n) 之间存在 n 的正整数乘法 b 使得 b * c = n, 那么 c 一定小于 √n 【n =√n*√n】,而这与前提(不存在位于 [2,√n] 之间的乘法因子)相矛盾，因此假设不成立。 2. 对于任意一个大于 2 的正整数 n, 从 2 开始，把所有后面2的倍数置为已标记非质数，把所有后面3的倍数置为已标记非质数.....循环到 sqrt(n)，后面剩下的都是质数。 推导：在上述前提下，假设在 (√n, n] 之间还存在未标记非质数 m，那么必存在 a ∈ [2, √m] 和 b ∈ [√m, m) 使得 m = a*b, 并且 a ∈ [2, √n], 而这与之前 将 a 的所有倍数置为 已标记非质数矛盾，因此假设不成立。 (C/C++学习) 37. 关于力扣204. 计数质数的相关推导 标签：问题 一个 c++学习 假设 计数 学习 开始 大于 c++ 原文地址：https://www.cnblogs.com/tuihou/p/13130191.html
文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：(C/C++学习) 37. 关于力扣204. 计数质数的相关推导
文章链接：http://soscw.com/essay/85083.html
文章标题：(C/C++学习) 37. 关于力扣204. 计数质数的相关推导
文章链接：http://soscw.com/essay/85083.html
评论
亲，登录后才可以留言！