试除法判定质数

给定 n 个正整数 ai，判定每个数是否是质数。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个正整数 ai。

输出格式

共 n 行，其中第 i 行输出第 i 个正整数 ai 是否为质数，是则输出 Yes，否则输出 No。

数据范围

1≤n≤100,
1≤ai≤2^31−1

输入样例：

1
2
3
2
2
6

输出样例：

1
2
Yes
No

代码

个人代码
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
#include<bits/stdc++.h>
using namespace std;
// 数据范围的情况
#define ll long long
int main() {
	int m;cin>>m;
	while(m--){
		ll val,i;cin>>val;
        // 特殊数据如1，2的情况
		if (val == 1) {
			cout<<"No"<<endl;
			continue;
		}
		for(i = 2;i * i <= val;i++){
			if (val % i == 0) {
				cout<<"No"<<endl;
				break;
			}
		}if (i * i > val) {
			cout<<"Yes"<<endl;
		}
		
	}	
}
/*
2
2
6
*/
题解
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
#include <iostream>
#include <algorithm>

using namespace std;

bool is_prime(int x)
{
    if (x < 2) return false;
    // 这里 用x/i 可以防止
    for (int i = 2; i <= x / i; i ++ )
    
        if (x % i == 0)
            return false;
    return true;
}

int main()
{
    int n;
    cin >> n;

    while (n -- )
    {
        int x;
        cin >> x;
        if (is_prime(x)) puts("Yes");
        else puts("No");
    }

    return 0;
}

分解质因数

给定 n 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个正整数 ai。

输出格式

对于每个正整数 ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。

每个正整数的质因数全部输出完毕后，输出一个空行。

数据范围

1≤n≤100,
2≤ai≤2×10^9

输入样例：

1
2
3
2
6
8

输出样例：

1
2
3
4
2 1
3 1

2 3

代码

个人代码
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void say (ll x) {
    /* 没看板子之前在这里寄了 需要考虑数据范围
    
    	for(long long i=2;i <= x;i++)
    	当时想法是寻找因为i的大小被改变过，导致 当我们在寻找i是否为x的质数时可能 i * i 已经大于x了
    	但是 我们假设 a * b = m;
    	a 《 b ;那必然不可能 m 比 a * a小惯性思维害我不浅啊由于数据没有考虑1的情况需要在数据最后判断  
    */
	for(long long i=2;i <= x/i;i++){
		int cnt = 0;
		while(x % i == 0){
			cnt++;
			x/=i;
		}
		if (cnt != 0) {
			printf("%lld %d\n",i,cnt);
		}
	}
	if (x > 1) {
		printf("%d %d",x,1);
	}
}
int main() {
	int n;cin>>n;
	while(n--){
		int temp;cin>>temp;
		say(temp);
	}
}
/*
	2
	6
	8

*/
题解
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
#include <iostream>
#include <algorithm>

using namespace std;

void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        divide(x);
    }

    return 0;
}


筛质数

给定一个正整数 n，请你求出 1∼n 中质数的个数。

输入格式

共一行，包含整数 n。

输出格式

共一行，包含一个整数，表示 1∼n 中质数的个数。

数据范围

1≤n≤10^6

输入样例：

1
8

输出样例：

1
4

代码

个人代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
	ps：如果一个数被证明是质数那么 所有莫它为0的数便不是质数每获得一个质数便不断将它所有的倍数置为不可能是质数
	
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1001000;
bool record[N];
int main() {
	int n;cin>>n;
	int res = 0;
	for(int i=2;i<=n;i++){
		if (!record[i]) {
			res++;
			for(int k=2;k * i<=n;k++){
				record[k * i] = true;
			}
		}
	}
	printf("%d",res);
}
题解
朴素筛法
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
#include <iostream>
#include <algorithm>

using namespace std;

const int N= 1000010;

int primes[N], cnt;
bool st[N];

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

int main()
{
    int n;
    cin >> n;

    get_primes(n);

    cout << cnt << endl;

    return 0;
}

线性筛法
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
#include <iostream>
#include <algorithm>

using namespace std;

const int N= 1000010;

int primes[N], cnt;
bool st[N];

/*
	没获得一个数我们便将他和所有的质数做乘积将所有的乘积都置为非

*/
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main()
{
    int n;
    cin >> n;

    get_primes(n);

    cout << cnt << endl;

    return 0;
}


扩展

筛法：

最普通的筛法 O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
void get_primes2(){
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt++]=i;//把素数存起来
        for(int j=i;j<=n;j+=i){//不管是合数还是质数，都用来筛掉后面它的倍数
            st[j]=true;
        }
    }
}
/*
	思路： 一个数的所有倍数必定不是质数
*/

诶氏筛法 O(nloglogn)

1
2
3
4
5
6
7
8
9
10
11
void get_primes1(){
    for(int i=2;i<=n;i++){
        if(!st[i]){
            primes[cnt++]=i;
            for(int j=i;j<=n;j+=i) st[j]=true;//可以用质数就把所有的合数都筛掉；
        }
    }
}
/*
	一个和数必定由某个质数的倍数组成
*/

线性筛法 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
oid get_primes(){
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}
/*
	思路： 每一个和数都可以被一堆的质数汇总而成我们尽可能的取减少他的重复赋值，也就是说让每一个和数的质数序列只能被唯一标识采用的方法可以让他的序列变得有序，那么对于一个序列来说新的元素只能小于等于最小元素即可
	证明 对于任意和数m他的最小质因子为 n 当我们达到 m / n 时 便会把他筛掉
*/