TA的每日心情 | 慵懒 2016-4-21 12:07 |
---|
签到天数: 3 天 连续签到: 1 天 [LV.2]偶尔看看I 累计签到:3 天 连续签到:1 天
|
马上加入,结交更多好友,共享更多资料,让你轻松玩转电力研学社区!
您需要 登录 才可以下载或查看,没有账号?立即加入
×
素数定义:质数又称素数。指在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数。换句话说,只有两个正因数(1和自己)的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着很重要的地位。
1 L7 [; R. P% |$ b* Q* d8 d* g* F2 Z" W/ ]' G" i5 |
素数是算法中经常提到的一种数的类型,求一个正整数的所有素数因子也是很多算法中经常用到的,今天在做一道算法题时也遇到了素数的求解,故在此记录一下,以备后用!
1 L$ y' ^" J) Y$ c" b, W; Q. ~. h3 R3 H s0 X2 M8 v0 t
#include <iostream>( a/ D' _% ?: R+ x
using1 ]% Y+ j& Y/ @
namespace std;, S; B7 Q; }8 D
( H u1 I' |9 c9 D/ Fvoid PrimaryCal(int num); w9 n4 O8 p7 b- I
{
$ B$ x( o/ r! e% {) }2 b- k H for(int i=2;i*i<=num;i++), y" {2 b ^9 Y! C
{
6 y- y- N; S% c' x7 L; H while(num%i==0)
* n* S" w& K; m% {) k {
% K; x, A, f) M+ _4 ^ cout<<i<<"
! J- Q( v: w' C C";) m; v/ R5 r8 `' ^* f: O
num/=i;2 j0 w6 x$ G# z# C; t2 e7 S% r
}
5 ?$ c7 K6 g6 x# s }% e( n5 h6 L8 |, ?3 M. E
if(num!=1)
) ?2 M, m/ H8 X. b# T- g0 I& v' J* l {
- H4 E2 v* k' x: O: j cout<<num;0 O2 q$ |: k6 E% d
}
9 i- S' v& ]" W$ ^}
: B: D" Y# i$ `* m9 q% ]7 ]) N
int main(void)4 P* M. Y2 c" n- _$ P" G) I$ \/ N7 N
{! O% |) e' x+ P- |/ E8 \+ N
for(int i=10;i<=100;i++)
8 q/ e( z% S3 z: q2 M2 C* X {7 k4 @/ t& w/ H$ ] F) M6 m5 [
cout<<i<<" = ";
+ r) Y% u5 A8 v PrimaryCal(i);
, u2 G u, m9 @- {3 B% F p5 @/ P$ v cout<<endl;
0 D' w; S, {8 Q/ N2 N }4 N% T9 ~/ \. w" N8 J& y
return6 c1 U4 R% w# Y" I- O: P L' s- l
-1;8 _& A B7 b; Y8 k6 S
} |
|