對於任何正整數x，其約數的個數記作g(x)。例如g(1)=1、g(6)=4。
如果某個正整數x滿足：g(x)>g(i) 0<i<x，則稱x為反質數。例如，整數1，2，4，6等都是反質數。
基本介紹
- 中文名：反素數
- 外文名：Anti-prime number
- 類型：數學
- 性質：從2開始連續的質數
- 分類：術語
- 來源：[HAOI2007]
性質,算法實現,
性質
性質一:一個反素數的質因子必然是從2開始連續的質數.
性質二:p=2^t1*3^t2*5^t3*7^t4.....必然t1>=t2>=t3>=....
算法實現
- 40分思路：
- 最佳化前
考慮直接暴力枚舉xx以及xx的因數，時間複雜度約為O(n^2O(n2log_2log2n)n)。
- 最佳化後
還是考慮直接暴力枚舉xx，但是我們可以通過最佳化枚舉因數的時間複雜度來降低整個程式的時間複雜度，這種方法的時間複雜度約為O(nO(nlog_2log2nn\times×sqrt(t))sqrt(t))。
100100分（滿分）思路：
什麼是反素數？
反素數就是區間內約數個數最多的那個數。根據題目要求，如果有多個滿足，選取最大的一個。
上文的引用部分摘自@stupid_one的部落格園，有刪改。
很顯然題目要求的區間就是[1,n][1,n]。那么我們怎么求反素數呢？
如果我們設p{}p為指數，k{}k為指數的話，那么如果一個數xx可以被分成如下形式。
x=\prod_{i=1}^{n}{p_i^{k_i}}x=∏i=1npiki。
那么xx的因數個數就是\prod_{i=1}^{n}{k_i+1}∏i=1nki+1。
如果設p_ipi嚴格遞增，並且k_i=0ki=0也算在內，則如果k_x<k_ykx<ky並且x<yx<y，那么顯然這個數不可能是反素數，因為交換k_xkx和k_yky會更好。 所以當p_ipi遞增時k_iki是遞減的，這個數xx才可能是反素數。
所以我們可以據此搜尋。
素數表可以篩一波，也可以這樣：
因為前12個素數的積>2 \times 10^9>2×109，所以最多用到12個素數，手動打素數表即可。
思路和代碼分別來自@羅愷的部落格以及@Goes的部落格。
最佳化前的40 分代碼（用時7000ms）：
#include <cstdio>int yz(int t) { int ans=0; for(int i=1; i<=t; i++) { if(t%i==0) { ans++; } } return ans;}bool pd(int x) { int dz=yz(x); for(int i=1; i<=x-1; i++) { if(yz(i)>=dz) { return false; } } return true;}int main() { int n=0; scanf("%d",&n); for(int i=n; ; i--) { if(pd(i)==true) { printf("%d",i); break; } } return 0;}最佳化後的40分代碼（用時6104ms ）：
#include <cstdio>#include <cmath>int yz(int t) { int ans=0; int mj=sqrt(t); for(int i=1; i<=mj; i++) { if(t%i==0) { ans+=2; } } if(mj*mj==t) { ans--; } return ans;}bool pd(int x) { int dz=yz(x); for(int i=1; i<=x-1; i++) { if(yz(i)>=dz) { return false; } } return true;}int main() { int n=0; scanf("%d",&n); for(int i=n; ; i--) { if(pd(i)==true) { printf("%d",i); break; } } return 0;}100分代碼：
#include<iostream>#include<cstdio>#include<cstring>using namespace std;long long p[20]= {0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};long long maxn=-1,ans=-1;long long n=0;void get(long long m,long long f,long long t,long long pr) { //f為當前質數的編號，當前指數<pr//t為當前約數的個數， m表示當前可能成為最優解的數 if(t>maxn || (t==maxn && m<ans)) { //更新最優解 ans=m,maxn=t; } long long i=m,j=0; long long nt=0; while(j<pr) { //j表示的是當前正在搜尋的指數 j++; if(n/i<p[f]) { //若不滿足條件就跳出循環（i表示的是當前的m） break; } nt=t*(j+1),i*=p[f];//更新新數以及它的因子個數。 if(i<=n) { //若i（即當前的m）在區間[1,n]內就繼續搜尋。 get(i,f+1,nt,j); } }}int main() { scanf("%lld",&n); get(1,1,1,30); printf("%lld",ans); return 0;}