夢に僕らで帆を張って
来るべき日のために夜を超え

标签 素数 下的文章

September 26, 2019

洛谷P1463/POI2002/HAOI2007 反素数

题意:求不大于 $n$ 的最大高合成数。高合成数指一个数,任何比它小的自然数的因子数目均比这个数的因子数目少。数据范围: $1 \le N \le 2000000000$题解:对于一个数 $x$ ,由算术基本定理$$x=\prod p_i^{a_i}$$则其因子数目为$$\prod (a_i+1)$$ 根据贪心,在因子数目数目一定时,$x$ 应为最小,此时 $x$ 才为高合成数。不妨设 $p...
September 26, 2019

素数判断

素数判断一、素数的定义质数(prime number)又称素数,有无限个。质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。注意 $1$ 不是素数也不是合数。二、判断一个数是否为素数由定义可得,一个数 $n$ 为素数当且仅当它只含因数 $1$ 和它本身。于是可从 $2$ 枚举到 $n-1$ 判断其是否为 $n$ 的因数。inline bool isPrime(int x){ ...