小白的刷题笔记一（质因数分解）

最近在复习C语言基础，刷到了这道题：


1098：质因数分解

时间限制: 1000 ms 内存限制: 65536 KB
提交数: 22139 通过数: 11165
【题目描述】
已知正整数n是两个不同的质数的乘积，试求出较大的那个质数。

【输入】
输入只有一行，包含一个正整数 n。

对于60%的数据，6≤n≤1000。

对于100%的数据，6≤n≤2×109。

【输出】
输出只有一行，包含一个正整数 p，即较大的那个质数。

【输入样例】
21
【输出样例】
7

因为在复习循环，所以用的双重循环嵌套，但是后面时间超出了。
WA代码如下：

#include <iostream>
#include <cmath>
using namespace std;
bool isprime(int a);
int main(int argc, char** argv) {
	int n;
	cin>>n;
	int i,j;
	for(i=2;i<=n/2;i++)
	{
		for(j=2;j<=n/2;j++)
		{
			if(i*j==n)
			{
				if(isprime(i)==true&&isprime(j)==true)
				{
					cout<<j;
其实这里可以直接输出j而不用判断i,j，是因为j为内层循环，j肯定是较大的质数。
					return 0;
// if(i<j)
// {
// cout<<j;
// break;
// }
// else
// {
// cout<<i;
// break;
// }
				}
			}
		}
	}
	return 0;
}
bool isprime(int a)
{
	int m;
	for(m=2;m*m<=a;m++)
	{
		if(a%m==0)
		return false;
	}
	return true;
}

当然运行超时了，我本以为是双重循环应该没问题，结果我在双重循环里还调用了我自己写的判断素数的函数，导致了运行超时。


所以这是一个三重循环了，时间复杂度应该是O（n^3）。

后面去搜了一下一位大佬的博客，简化了判断素数的步骤，但是还是超时了。
大佬博客：

https://blog.csdn.net/liangdagongjue/article/details/77895170

时间复杂度O（n^3）太可怕了，优化后的WA代码：

#include <iostream>
#include <cmath>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
bool isprime(int a);
int main(int argc, char** argv) {
	int n;
	cin>>n;
	int i,j;
	for(i=2;i<=n/2;i++)
	{
		for(j=2;j<=n/2;j++)
		{
			if(i*j==n)
			{
				if(i%2!=0&&j%2!=0)
				{
					if(isprime(i)==true&&isprime(j)==true)
					{	
					cout<<j;
					return 0;
					}
				}
			}
		}
	}
	return 0;
}
bool isprime(int a)
{
	int m;
	for(m=2;m*m<=a;m+=2)
	{
		if(a%m==0)
		return false;
	}
	return true;
}

实在是气急了，搜了一下别人的题解：

https://blog.csdn.net/u011815404/article/details/79329624

AC代码：

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int n;
    int i,j;
 
    cin>>n;
    for(i=2; i<=sqrt(n); i++) //两个不同质数，其中必有一个≤sqrt(n)
    {
        if(n%i==0)//找到质数
        {
            cout<<n/i<<endl;//较大质数=n/较小质数，输出
            break;//输出后，终止
        }
    }
 
    return 0;
}

单层循环，n/i得解，秒啊！

赶作业去了…