算法题解之质数问题

时间：2021-07-09 13:21:18

        求质数是一个常见的问题，但是求质数的难点在于复杂度上的拿捏，一些面试官都知道判断一个数是否是质数并难不倒大多数人，于是他们可能会让问题更加深入，比如复杂度的控制等等。本文主要讲解一些面试或者笔试中可能会碰到的题目。

1.判断质数

        首先从最基本的判断质数开始讲解，从质数定义出发：一个数只能被1和其本身整除，则该数为质数。判断一个数a是否是质数，则判断是否在2-(a-1)存在一个整数能够整除a，如果存在，则说明不是质数，如果不存在则其是质数。
解法1，直接判断2-(n-1)是否存在着能够整除n的数。时间复杂度O(n)。 
package prime;
import java.util.*;
public class IsPrime {
	public static boolean isprime(int n)
	{
		if(n==1)
			return false;
		else
		{
			int i=2;

			while(i<n)
			{
				if(n%i!=0)
					i+=1;
				else
					return false;
			}
			return true;
		}
	}
	public static void main(String[] args)
	{
		Scanner sc=new Scanner(System.in);
		while(sc.hasNextInt())
		{
			int n=sc.nextInt();
			if(isprime(n))
				System.out.println(n+"是质数");
			else
				System.out.println(n+"不是质数");
		}
	}

}
运行结果： 
2
2是质数
3
3是质数
5
5是质数
6
6不是质数
8
8不是质数
解法2，可以降低时间复杂度，因为若存在一个数a能够整除n，那么n/a也是一个整数，并且如果a<n^(1/2)，那么n/a必然大于n^(1/2)。所以可以将复杂度降低到n^(1/2)。注意若n^(1/2)不是整数得向上取整。
代码如下： 
package prime;
import java.util.*;
public class IsPrime {
	public static boolean isprime(int n)
	{
		if(n==1)
			return false;
		else
		{
			int i=2;

			while(i<(int)Math.sqrt(n)+1)
			{
				if(n%i!=0)
					i+=1;
				else
					return false;
			}
			return true;
		}
	}
	public static void main(String[] args)
	{
		Scanner sc=new Scanner(System.in);
		while(sc.hasNextInt())
		{
			int n=sc.nextInt();
			if(isprime(n))
				System.out.println(n+"是质数");
			else
				System.out.println(n+"不是质数");
		}
	}

}
运行结果如下： 
2
2是质数
3
3是质数
4
4不是质数
5
5是质数
6
6不是质数
7
7是质数
8
8不是质数

2.求质数个数一般方法

        前面已经讲述了判断一个数是否为质数，而现在我们稍微提升一下问题，即求1-N之间质数个数问题。那么我们第一时间想到的就是1-N逐个遍历然后进行。
代码如下： 
package prime;
import java.util.*;
public class IsPrime {
	//判断是否为质数
	public static boolean isprime(int n)
	{
		if(n==1)
			return false;
		else
		{
			int i=2;

			while(i<(int)Math.sqrt(n)+1)
			{
				if(n%i!=0)
					i+=1;
				else
					return false;
			}
			return true;
		}
	}
	//计算n以内的质数个数
	public static int countPrime(int n)
	{
		int ans=0;
		for(int i=2;i<=n;i++)
		{
			if(isprime(i))
				ans+=1;
		}
		return ans;
	}
	public static void main(String[] args)
	{
		Scanner sc=new Scanner(System.in);
		while(sc.hasNextInt())
		{
			int n=sc.nextInt();
			long t1=System.currentTimeMillis();
			int ans=countPrime(n);
			long t2=System.currentTimeMillis();
			System.out.println("小于等于"+n+"的质数个数为："+ans);
			System.out.println("计算时间为:"+(t2-t1));
		}
	}

}
运行代码结果如下： 
1000
小于等于1000的质数个数为：168
计算时间为:1
10000
小于等于10000的质数个数为：1229
计算时间为:1
100000
小于等于100000的质数个数为：9592
计算时间为:21
1000000
小于等于1000000的质数个数为：78498
计算时间为:482
        可以看出数据变庞大之后，每一个样例输入求解时间也会陡增，假设样例个数为t，每次输入为n，其中n和t都小于10^6，那么这样一来数据复杂度为O(t*n*n^(1/2))。如果针对样例比较少的甚至只有一个样例时，时间复杂度近似为O(n*n^(1/2))，该方法适用，但是如果样例接近n，那么该复杂度大于O(n^2)，那么该方法显得时间复杂度过高。
        不过对于该一般方法，还可以进行优化，即配合使用打表法，借助于随机访问数组的复杂度为O(1)。
代码如下： 
package prime;
import java.util.*;
public class IsPrime {
	private static int max_int=1000000;
	//判断是否为质数
	public static boolean isprime(int n)
	{
		if(n==1)
			return false;
		else
		{
			int i=2;

			while(i<(int)Math.sqrt(n)+1)
			{
				if(n%i!=0)
					i+=1;
				else
					return false;
			}
			return true;
		}
	}
	//计算n以内的质数个数
	public static int[] countPrime()
	{
		int[] res=new int[max_int+1];
		for(int i=2;i<=max_int;i++)
		{
			if(isprime(i))
				res[i]=1;
		}
		return res;
	}
	public static void main(String[] args)
	{
		Scanner sc=new Scanner(System.in);
		long t1=System.currentTimeMillis();
		//打表
		int[] res=countPrime();
		long t2=System.currentTimeMillis();
		System.out.println("打表花费时间："+(t2-t1));
		//求前缀和
		for(int i=1;i<=max_int;i++)
			res[i]+=res[i-1];
		while(sc.hasNextInt())
		{
			int n=sc.nextInt();
			long t3=System.currentTimeMillis();
			int ans=res[n];
			long t4=System.currentTimeMillis();
			System.out.println("小于等于"+n+"的质数个数为："+ans);
			System.out.println("计算时间为:"+(t4-t3));
		}
	}

}



运行程序结果如下： 
打表花费时间：482
1000
小于等于1000的质数个数为：168
计算时间为:0
10000
小于等于10000的质数个数为：1229
计算时间为:0
100000
小于等于100000的质数个数为：9592
计算时间为:0
1000000
小于等于1000000的质数个数为：78498
计算时间为:0
        从上面可以看出打表时间一定，但是每一次的求解相当于O(t),前缀和O(n)，所以总的时间就是打表花费的时间为O(n*n^(1/2))。所以时间复杂度降低了不少，配合打表法特别适用于有很多样例的题目。

3.筛法求质数个数

       上述的一般方法求质数个数时，样例比较多时，时间复杂度是大于平方级的，当数据庞大时，那么时间复杂度也会过高。下面通过一种线性的方法进行求解--筛法求质数。
何谓筛法呢，筛法就是每一次判断的时候不再重复判断，保证每个数只会被它的最小质因数筛去。
代码如下，可以看出，用筛法求质数时，时间复杂度为O(n),求前缀和时间复杂度为O(n),对所有样例进行求解，则O(t)，所以总的时间复杂度为O(2*n+t)，属于线性级别。明显优于一般方法。 
package prime;
import java.util.*;
public class IsPrime1 {
	public static int max_int=1000000;
	public static int[] sieveMethod()
	{
		int[] res=new int[max_int+1];
		for(int i=0;i<=max_int;i++)
			res[i]=1;
		res[0]=res[1]=0;
		//时间复杂度为O(n)
		for(int i=2;i<=(int)Math.sqrt(max_int)+1;i++)
		{
			int j=i;
			int k=j;
			while(j*k<=max_int)
			{
				res[j*k]=0;
				k+=1;
			}
		}
		return res;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		long t1=System.currentTimeMillis();
		int[] res=sieveMethod();
		long t2=System.currentTimeMillis();
		System.out.println("筛法求数组所用时间为："+(t2-t1));
		//求res数组的前缀和，O(n)
		for(int i=1;i<=max_int;i++)
			res[i]+=res[i-1];
		//对于样例输入进行求解，假设样例为t，则时间复杂度为O(t*1)
		while(sc.hasNextInt())
		{
			int n=sc.nextInt();
			//随机访问数组，O(1)
			long t3=System.currentTimeMillis();
			System.out.println("小于等于"+n+"的质数个数为："+res[n]);
			long t4=System.currentTimeMillis();
			System.out.println("该样例求解时间"+(t4-t3));
		}

	}

}
运行结果如下： 
筛法求数组所用时间为：16
1000
小于等于1000的质数个数为：168
该样例求解时间0
10000
小于等于10000的质数个数为：1229
该样例求解时间0
100000
小于等于100000的质数个数为：9592
该样例求解时间0
1000000
小于等于1000000的质数个数为：78498
该样例求解时间0
        比较该方法与一般方法的运行时间，可以明显看出筛法求质数的优势。



4.求任意两个数之间的质数个数

        其实题目还可以改变，现在将题目变为两个数之间的质数个数，这个题就会将打表法的优势体现的很清晰。相当于最终将问题转化为了前期工作的打表配合筛法，后期的随机访问即可。

代码如下： 

package prime;
import java.util.Scanner;
public class IsPrime2 {
	public static int max_int=1000000;
	public static int[] sieveMethod()
	{
		int[] res=new int[max_int+1];
		for(int i=0;i<=max_int;i++)
			res[i]=1;
		res[0]=res[1]=0;
		//时间复杂度为O(n)
		for(int i=2;i<=(int)Math.sqrt(max_int)+1;i++)
		{
			int j=i;
			int k=j;
			while(j*k<=max_int)
			{
				res[j*k]=0;
				k+=1;
			}
		}
		return res;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		long t1=System.currentTimeMillis();
		int[] res=sieveMethod();
		long t2=System.currentTimeMillis();
		System.out.println("筛法求数组所用时间为："+(t2-t1));
		//求res数组的前缀和，O(n)
		for(int i=1;i<=max_int;i++)
			res[i]+=res[i-1];
		//对于样例输入进行求解，假设样例为t，则时间复杂度为O(t*1)
		while(sc.hasNextInt())
		{
			int a=sc.nextInt();
			int b=sc.nextInt();
			//随机访问数组，O(1)
			long t3=System.currentTimeMillis();
			System.out.println(a+"到"+b+"的质数个数为："+(res[b]-res[a-1]));
			long t4=System.currentTimeMillis();
			System.out.println("该样例求解时间"+(t4-t3));
		}

	}

}
运行程序，结果如下： 

筛法求数组所用时间为：19
1 9
1到9的质数个数为：4
该样例求解时间0
20 100
20到100的质数个数为：17
该样例求解时间0
500 10000
500到10000的质数个数为：1134
该样例求解时间0
600 100000
600到100000的质数个数为：9483
该样例求解时间0
15890 999999
15890到999999的质数个数为：76646
该样例求解时间1
观察上述结果，可以得知素数筛法并且打表适用于样本很多的或者求任意区间的素数的比较具有优势。





标签：

相关文章