素数专题

发表于 | 更新于 | 分类于 | 阅读次数：

判断n是否为素数 ( sqrt(n)时间复杂度)

1
2
3
4
5
6
7
8
9
10
11
12
int isprime(int n)
{
        if(n<=1)
                return 0;
        int sqr=(int)sqrt(1.0*n);
        for(int i=2;i<=sqr;i++)
        {
                if(n%i==0)
                        return 0;
        }
        return 1;
}

求100以内的素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>
#include <math.h>
int isprime(int n)
{
        if(n<=1)
                return 0;
        int sqr=(int)sqrt(1.0*n);
        for(int i=2;i<=sqr;i++)
        {
                if(n%i==0)
                        return 0;
        }
        return 1;
}

int prime[101],pNum=0;
int p[101]={0};
void Find_Prime()
{
        for(int i=1;i<101;i++)
        {
                if(isprime(i))
                {
                        prime[pNum++]=i;//存储素数i
                        p[i]=1;
                }
        }
}


int main()
{
        Find_Prime();
        for(int i=0;i<pNum;i++)
                printf("%d ",prime[i]);
}

分解质因数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <stdio.h>
#include <math.h>
int maxn=10010;

int is_prime(int n)
{
	if(n==1)
		return 0;
	int sqr=(int)sqrt(1.0*n);
	for(int i=2;i<=sqr;++i)
		if(n%i==0)
			return 0;
	return 1;
}

int prime[10010],pNum=0;

//获取素数表
void Find_Prime()
{
	for(int i=1;i<maxn;++i)
		if(is_prime(i))
			prime[pNum++]=i;
}

struct factor
{
	int x,cnt;//x为质因子，cnt为其个数
}fac[10];

int main()
{
	Find_Prime();
	int n,num=0;//num为n的不同质因子的个数
	scanf("%d",&n);
	if(n==1)
		printf("1=1");//特判1的情况
	else
	{
		printf("%d=",n);
		int sqr=(int)sqrt(1.0*n);
		//枚举根号n以内的质因子
		for(int i=0;i<pNum&&prime[i]<=sqr;++i)
		{
			if(n%prime[i]==0)
			{
				fac[num].x=prime[i];//记录该因子
				fac[num].cnt=0;
				//计算出质因子prime[i]的个数
				while(n%prime[i]==0)
				{	
					fac[num].cnt++;
					n/=prime[i];
				}
				num++;//不同质因子的个数加1
			}
			if(n==1)
				break;//及时退出循环，节省点时间
		}

		//如果不能被根号n以内的质因子除尽，那么一定有一个大于根号n的因子
		if(n!=1)
		{
			fac[num].x=n;
			fac[num++].cnt=1;
		}
		//按照格式输出结果
		for(int i=0;i<num;++i)
		{
			if(i>0)
				printf("*");
			printf("%d",fac[i].x);
			if(fac[i].cnt>1)
				printf("^%d",fac[i].cnt);
		}
	}
	
}
凡希 wechat
喜欢所以热爱，坚持干货分享，欢迎订阅我的微信公众号
呐，请我吃辣条