当前位置：网站首页>Problems related to prime numbers - small notes

Problems related to prime numbers - small notes

2022-08-02 15:34:00 【Old stubborn and cute】

Prime related issues

Prime Numbers and prime number,在ACMRelated problems often arise in the,例如 P1029 NOIP2001 普及组最大公约数和最小公倍数问题、P2043 质因子分解、P3383 【模板】线性筛素数等等,Today to talk about these topics in common.

奇技淫巧-欧几里得算法

欧几里得算法又称辗转相除法,是指用于计算两个非负整数a,b的最大公约数.应用领域有数学和计算机两个方面.计算公式 $g c d (a, b) = g c d (b, a m o d b)$ .

inline int gcd(int x,int y)
{
    
	if(y==0) return x;
	return gcd(y,x%y);
}

例题如下：

[NOIP2001 普及组] 最大公约数和最小公倍数问题

题目描述

输入两个正整数 $x_0, y_0$ ,求出满足下列条件的 $P, Q$ 的个数：

$P, Q$ 是正整数.
要求 $P, Q$ 以 $x_0$ 为最大公约数,以 $y_0$ 为最小公倍数.

试求：满足条件的所有可能的 $P, Q$ 的个数.

输入格式

一行两个正整数 $x_0, y_0$ .

输出格式

一行一个数,表示求出满足条件的 $P, Q$ 的个数.

样例 #1

样例输入 #1

3 60

样例输出 #1

提示

$P, Q$ 有 $4$ 种：

$3, 60$ .
$15, 12$ .
$12, 15$ .
$60, 3$ .

对于 $100\%$ 的数据, $\le x_0, y_0 \le {10}^5$ .

【题目来源】

NOIP 2001 普及组第二题

题解

First, you need to understand the greatest common divisor and least common multiple is how to calculate.

要是 $a$ 和 $b$ 的最大公约数为 $m$ 、最小公倍数为 $n$ ,则可以推断出 $a * b / m = n$ ,而且 $a / m$ 和 $b / m$ 的最大公约数是 $1$ .至于为什么？emmm,Mathematics intuition is like this.

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int sd(int a,int b)
{
    
	if(a%b==0)
	{
    
		return b;
	}
	else
	{
    
		return sd(b,a%b);
	}
}
int main()
{
    
	int n,m;
	while(~scanf("%d%d",&n,&m))
	{
    
		if(m%n!=0)
		{
    
			printf("0\n");
			continue;
		}
		int k=m/n;
		int sum=0;
		for(int i=1;i<sqrt(k);i++)
		{
    
			if(k%i==0)
			{
    
				int q=k/i;
				if(sd(q,i)==1)
				{
    
					sum++;
				}
			}
		}
		printf("%d\n",sum*2);
	}
	return 0;
}

质因子分解

题目描述

对N!进行质因子分解.

输入格式

输入数据仅有一行包含一个正整数N,N<=10000.

输出格式

输出数据包含若干行,每行两个正整数p,a,中间用一个空格隔开.表示N!包含a个质因子p,要求按p的值从小到大输出.

样例 #1

样例输入 #1

样例输出 #1

提示

10!=3628800=(2^8)*(34)*(5^2)*7

题解

This is going to use the definition of prime,首先可以知道 Decomposition of a number to the last must be the product of a pile of prime Numbers.

So assuming that the number is $n$ ,As long as from $2$ 开始一直到 $n$ Decomposition of the number,Don't have to distinguish the prime,Because each quality factor we all have been,Until can't except,Later can also won't appear in addition to the multiples of the number is the number of,Equivalent to have screen off,So the last will be broken down into the product of prime Numbers.

#include<iostream>
using namespace std;
int a[10001]={
    0},n; //数组很大,Remember driving in the outside oh
int main()
{
    
	cin>>n;
	for (int i=2;i<=n;i++) //1就不用了,从2到n一个一个来
	{
    
	 	int i2=i;  //备份一下,Or I'll get rid of the
		for (int j=2;j<=i;j++)  //从2Began to determine whether can be divided exactly by
			while (i2%j==0) {
    a[j]++; i2/=j;} 
            //记得使用while,不是if,To what a
	}
	for (int i=1;i<=10000;i++)  //输出
    	if (a[i]!=0)
    		cout<<i<<" "<<a[i]<<endl;
}

判断质数方法-总结

A more common way to determine

bool IsPrime()
{
    
	for(int i=2;i<=sqrt(n);i++)
	{
    
		if(n%i==0) return false;
	}
	return true;
}

Eratosthenes筛选法（质数的倍数一定不是质数）

同时对于每个x,把大于等于x的平方的x的倍数标记为合数.

void isprime(int n)///筛选1-n的素数
{
    
    memset(vis,0,sizeof(vis));
    int m = sqrt(n + 0.5);
    for(int i = 2; i <= m; i++)
    {
    
        if(!vis[i])
        {
    
            for(int j = i * i; j <= n; j += i)
                vis[j] = 1;
        }
    }
}

线性筛法

Each sum Numbers will only be its minimum quality factor screen at a time,时间复杂度 $O (n)$

int v[maxn],prime[maxn];
void primes(int n)
{
    
	memset(v,0,sizeof(v));///最小质因子
	m=0;
	for(i=2;i<=n;i++)
	{
    
		if(v[i]==0)///i为质数
		{
    
			v[i]=i;
			prime[++m]=i;
		}
		///给当前的数i乘上一个质因子
		for(j=1;j<=m;j++)
		{
    
			///i有比prime[i]更小的质因子,或者超出n的范围
			if(prime[j]>v[i]||prime[j]>n/i) break;
			v[i*prime[j]]=prime[j];
		}
	}
	for(i=1;i<=m;i++)
		cout<<prime[i]<<endl;
}

The fastest template

There is also a read on the Internet a method of judging prime,这是当时ccpcAlso used when a template.

bool isPrime( int num )
{
    
	//两个较小数另外处理
    if(num ==2|| num==3 )
        return 1 ;
    //不在6的倍数两侧的一定不是质数
        if(num %6!= 1&&num %6!= 5)
             return 0 ;
        int tmp =sqrt( num);
           //在6的倍数两侧的也可能不是质数
        for(int i= 5;i <=tmp; i+=6 )
             if(num %i== 0||num %(i+ 2)==0 )
                   return 0 ;
        //排除所有,剩余的是质数
        return 1 ;
}

This is I see the judgment of the primes the fastest a way

质数筛

For some problem solving which primes,可以先打表,然后直接输出,这样会快一点.But this practice is in time most commonly before playing table,How to reduce the time playing table has become top priority.This problem is to solve this problem.

【模板】线性筛素数

题目背景

本题已更新,从判断素数改为了查询第 $k$ 小的素数
提示：如果你使用 cin 来读入,建议使用 std::ios::sync_with_stdio(0) 来加速.

题目描述

如题,给定一个范围 $n$ ,有 $q$ 个询问,每次输出第 $k$ 小的素数.

输入格式

第一行包含两个正整数 $n, q$ ,分别表示查询的范围和查询的个数.

接下来 $q$ 行每行一个正整数 $k$ ,表示查询第 $k$ 小的素数.

输出格式

输出 $q$ 行,每行一个正整数表示答案.

样例 #1

样例输入 #1

样例输出 #1

提示

【数据范围】
对于 $100\%$ 的数据, $n = 10^8$ , $\le q \le 10^6$ ,保证查询的素数不大于 $n$ .

Data by NaCly_Fish.

#include <cstdio>
#include <cstring>

bool isPrime[100000010];
//isPrime[i] == 1表示：i是素数
int Prime[6000010], cnt = 0;
//Prime存质数

void GetPrime(int n)//筛到n
{
    
	memset(isPrime, 1, sizeof(isPrime));
	//以“每个数都是素数”为初始状态,逐个删去
	isPrime[1] = 0;//1不是素数
	
	for(int i = 2; i <= n; i++)
	{
    
		if(isPrime[i])//没筛掉 
			Prime[++cnt] = i; //i成为下一个素数
			
		for(int j = 1; j <= cnt && i*Prime[j] <= n/*不超上限*/; j++) 
		{
    
        	//从Prime[1],即最小质数2开始,逐个枚举已知的质数,并期望Prime[j]是(i*Prime[j])的最小质因数
            //当然,i肯定比Prime[j]大,因为Prime[j]是在i之前得出的
			isPrime[i*Prime[j]] = 0;
            
			if(i % Prime[j] == 0)//i中也含有Prime[j]这个因子
				break; //重要步骤.见原理
		}
	}
}

int main()
{
    
	int n, q;
	scanf("%d %d", &n, &q);
	GetPrime(n);
	while (q--)
	{
    
		int k;
		scanf("%d", &k);
		printf("%d\n", Prime[k]);
	}
	return 0;
}