中级天翼
3893 可怕的质因数经验值：0
题目描述 Description
给定一个正整数n(2<=n<=10000000)，求不超过n的有最多质因数（重复的质因数只算一个）的最小的数，且输出其不重复的质因数个数。
输入描述 Input Description
一个正整数n
输出描述 Output Description
一行，满足条件的数及其不重复的质因数个数，用空格隔开
样例输入 Sample Input
20
样例输出 Sample Output
6 2
数据范围及提示 Data Size & Hint
在不超过20的整数中，6有最多的质因数（2个）且最小（10，12，14，15，16，18，20的不重复的质因数都是2个，但是比6大）。
tle超时代码：
#include<iostream>
#include<cmath>
#pragma once
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;
int cnt[11000000],b[11000000],maxn,a;
int main(){
int n;
cin>>n;
for(int i=2;i<=n;i++){
for(int j=2;j<=i;j++){
if(b[j]==0&&i%j==0){
cnt[i]++;
for(int k=j*2;k<=n;k+=j){
b[k]=1;
}
}
}
}
for(int i=2;i<=n;i++){
if(cnt[i]>=maxn){
maxn=cnt[i];
}
}
for(int i=2;i<=n;i++){
if(cnt[i]==maxn){
a=i;
maxn=cnt[i];
break;
}
}
cout<<a<<" "<<maxn;
return 0;
}
丁博扬在2021-01-29 19:09:01追加了内容
可以用另一种方式
丁博扬在2021-01-29 19:21:58追加了内容
样例过了，就是怎么优化
丁博扬在2021-01-29 19:27:14追加了内容
顶
丁博扬在2021-01-29 19:30:55追加了内容
顶
中级启示者
你看这样筛行不行
筛质数
循环(int i=2;i<=sqrt(n);i++){
如果(a[i]==0){
循环(int j=i*2;j<=n;j+=i){
a[j]=1;
}
}
}
筛质因数
循环(int i=2;i<=n;i++){
如果(a[i]==0){
循环(int j=i;j<=n;j+=i){
b[j]++;
}
}
}
之后找出b数组中最大的元素
汪恺恒在2021-01-29 19:42:55追加了内容
先找最大值b数组最大值（和你的一样）
之后
for(int i=2;i<=n;i++){
if(b[i]==maxn){
pos=i;
break;
}
}
最后输出pos和maxn
