`
gushuizerotoone
  • 浏览: 174388 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

(math) SmoothNumbersHard --largest prime factor(最大质数因子)

阅读更多
http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm388

题目:求一系列数的最大质数因子
看代码,运行代码。a数组是标示哪个是质数的,1代表是质数,0代表是非质数。如果这个有个质数i计算过了,则含这个i因子的数都标为0
b数组时标示每个数的最大质数因子的,随着i的增大不断改变。
比如6,计算到i=2的时候 b[6]=2.但当计算到i=3的时候,b[6]=3,这才是它的最大质数因子

#include <iostream> 
#include <fstream> 
#include <math.h> 
#include <string> 
#include <vector> 
#include <algorithm> 
using namespace std; 

class SmoothNumbersHard 
{ 
public: 
	int countSmoothNumbers(int N, int k) 
	{ 
		int num =1;
		vector<int> a(N+1);//存是否还是质数的标识,1代表还是,0不是质数了
		vector<int> b(N+1);//存数的最大质数因子,b[4]=2,b[5]=5,b[6]=3...
		for (int i=2;i<=N;i++)
		{
			a[i]=1;
		}
		//质数因子不断增大
		for (int i=2;i<=N;i++)
		{

			if(a[i]==1){
				//这里不要忘了
				b[i] = i;
				for (int j=2;i*j<=N;j++)
				{
					//把含这个质数因子i的标为0,即标为0后表明这个数不是质数
					a[i*j] = 0;
					//i*j这个数的最大质数因子随着i的增大不断赋值,直到最大的那个
					b[i*j] = i;
				}
			}
		}

		for (int i = 2;i<=N;i++)
		{
			if (b[i] <= k)
			{
				num++;
			}
		}
		return num;
	} 
};
分享到:
评论

相关推荐

    commons-math3-3.6.1-API文档-中文版.rar

    commons-math3-3.6.1-API文档-中文版.rar commons-math3-3.6.1-API文档-中文版.rar commons-math3-3.6.1-API文档-中文版.rar commons-math3-3.6.1-API文档-中文版.rar commons-math3-3.6.1-API文档-中文版.rar ...

    commons-math3-3.6.1-API文档-中英对照版.zip

    赠送jar包:commons-math3-3.6.1.jar; 赠送原API文档:commons-math3-3.6.1-javadoc.jar; 赠送源代码:commons-math3-3.6.1-sources.jar; 赠送Maven依赖信息文件:commons-math3-3.6.1.pom; 包含翻译后的API文档...

    commons-math3-3.6.1-API文档-中文版.zip

    赠送jar包:commons-math3-3.6.1.jar; 赠送原API文档:commons-math3-3.6.1-javadoc.jar; 赠送源代码:commons-math3-3.6.1-sources.jar; 赠送Maven依赖信息文件:commons-math3-3.6.1.pom; 包含翻译后的API文档...

    commons-math3-3.1.1-API文档-中英对照版.zip

    赠送jar包:commons-math3-3.1.1.jar; 赠送原API文档:commons-math3-3.1.1-javadoc.jar; 赠送源代码:commons-math3-3.1.1-sources.jar; 赠送Maven依赖信息文件:commons-math3-3.1.1.pom; 包含翻译后的API文档...

    fmath-mathml-java-latex-mathml.jar.rar

    fmath-mathml-java-latex-mathml.jar.rar中包含3个jar,具体如下: fmath-latex-mathml-0.5.jar fmath-mathml-1.0.jar fmath-mathml-java-3.1.jar

    commons-math3-3.5-API文档-中英对照版.zip

    赠送jar包:commons-math3-3.5.jar; 赠送原API文档:commons-math3-3.5-javadoc.jar; 赠送源代码:commons-math3-3.5-sources.jar; 赠送Maven依赖信息文件:commons-math3-3.5.pom; 包含翻译后的API文档:...

    fmath-mathml-java.jar.rar

    《LaTeX与MathML之间的转换:fmath-mathml-java.jar的应用详解》 在信息技术领域,数学公式和符号的表达是不可或缺的一部分。LaTeX和MathML(Mathematics Markup Language)作为两种主流的数学公式表示方式,各有其...

    fmath-mathml-java-latex-mathml.jar.zip

    《LaTeX与MathML在Java环境中的转换工具详解》 在信息技术领域,LaTeX和MathML都是用于表示数学公式的强大工具。LaTeX是一种基于TeX的排版系统,广泛应用于科学和技术文档的编写,尤其在数学公式方面表现出色。而...

    commons-math3-3.5-API文档-中文版.zip

    赠送jar包:commons-math3-3.5.jar; 赠送原API文档:commons-math3-3.5-javadoc.jar; 赠送源代码:commons-math3-3.5-sources.jar; 赠送Maven依赖信息文件:commons-math3-3.5.pom; 包含翻译后的API文档:...

    fmath-mathml-java.zip

    《fmath-mathml-java.zip:Java处理Word数学公式的利器》 在现代文档处理中,Word文档中的数学公式往往成为复杂性和精确性的象征。在技术文档、学术论文或者教育资料中,数学公式起着至关重要的作用。对于开发者来...

    commons-math-2.2-API文档-中英对照版.zip

    赠送jar包:commons-math-2.2.jar; 赠送原API文档:commons-math-2.2-javadoc.jar; 赠送源代码:commons-math-2.2-sources.jar; 赠送Maven依赖信息文件:commons-math-2.2.pom; 包含翻译后的API文档:commons-...

    fmath-mathml-java

    fmath-mathml-java.jar 使用时大家可以自行进行下载,自己也找了好久

    commons-math3-3.4.1-API文档-中文版.zip

    赠送jar包:commons-math3-3.4.1.jar; 赠送原API文档:commons-math3-3.4.1-javadoc.jar; 赠送源代码:commons-math3-3.4.1-sources.jar; 赠送Maven依赖信息文件:commons-math3-3.4.1.pom; 包含翻译后的API文档...

    fmath-latex-mathml-0.5.jar

    LaTeXMathML可以通过Javascript语言将LaTeX表达式转换成为MathML语言,从而在 IE6/Firefox3 等支持MathML的浏览器上呈现较为完美的数学公式

    fmath-mathml-java-v2.1

    【fmath-mathml-java-v2.1】是一款基于Java平台的库,专门用于解析和渲染MathML(Mathematics Markup Language)格式的数学公式。MathML是一种XML标准,用于表示数学符号、表达式和数学文本,它使得在网页、应用程序...

    commons-math3-3.1.1.jar中文-英文对照文档.zip

    commons-math3-***.jar中文-英文对照文档.zip,java,commons-math3-***.jar,org.apache.commons,commons-math3,***,org.apache.commons.math3,jar包,Maven,第三方jar包,组件,开源组件,第三方组件,Gradle,apache,...

    commons-math3-3.6.1.jar

    在计算四参数的时候,我们需要进行矩阵计算,这个过程对精度要求贼高,我们需要借助于第三方的jar实现计算,才能保证精度,可以参考这篇博客:https://blog.csdn.net/qq_42811161/article/details/107809777 ...

    commons-math3-3.6.zip

    Apache Commons Math是一个强大的Java库,专注于提供各种数学和统计功能,用于进行科学计算。这个库在版本3.6.1中包含了"commons-math3-3.6.1.jar"等文件,它提供了广泛的功能,使得开发人员能够在Java环境中轻松...

    docx4j-3.3.7.jar fmath-mathml-java.jar jdom-2.0.6.jar

    标题和描述中提到的三个Java库文件——"docx4j-3.3.7.jar", "fmath-mathml-java.jar", 和 "jdom-2.0.6.jar",都是在Java开发环境中用于处理特定任务的重要组件。以下是关于这些库的详细解释: 1. **docx4j-3.3.7....

    commons-math3-3.4.1-API文档-中英对照版.zip

    赠送jar包:commons-math3-3.4.1.jar; 赠送原API文档:commons-math3-3.4.1-javadoc.jar; 赠送源代码:commons-math3-3.4.1-sources.jar; 赠送Maven依赖信息文件:commons-math3-3.4.1.pom; 包含翻译后的API文档...

Global site tag (gtag.js) - Google Analytics