Java笔记4|快速找素数的两种方法

Java笔记4|快速找素数的两种方法 1.构造素数表，不能被所有素数整出的数就是素数

//--输出前50个素数  
		int cnt = 1;
		int[]  prime = new int[50];
		prime[0] = 2;
		Mark:
		for(int xxx = 3;cnt < 50;xxx++)
		{
			for(int i = 0;i < cnt;i++)
			{
				if(xxx % prime[i] == 0) 
				{
					continue Mark;
				}
			}
			prime[cnt] = xxx;
			cnt++;
		}
		for(int k : prime)
		{
			System.out.print(k+" ");
		}
	

2.素数倍数标记，丢掉，剩下的就是素数

由于一定范围内素数本身比非素数少得多，因此标记并丢掉素数的倍数效率比较高。

	//素数倍数标记，素数的倍数丢掉，剩下的就是素数，更快！
		boolean [] isPre = new boolean [101];//输出100以内的素数 
		for(int i = 0;i < isPre.length;i++) {
			isPre[i] = true;//一开始假设都是素数，遇到不是素数的标记为false
		}
		for(int i = 2;i < isPre.length;i++)
		{
			if(isPre[i])
			{
				for(int j =2;j*i <= 100;j++)
				{
					isPre[i*j] = false;
				}
			}
		}
		for(int i = 0;i < isPre.length;i++) 
		{
			if(isPre[i])
			{
				System.out.print(i+" ");
			}
		}