This week you are again asked to write a program to find prime numbers, but the algorithm you will use is very different.
For given value of N (say, 30), first write down all the integers from 2 to N:
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
Delete all the multiples of the first number in the sequence (2):
2 3 5 7 9 11 13 15 17 19 21 23 25 27 29
Now move onto the next number (3) and do the same again:
2 3 5 7 11 13 17 19 23 25 29
Do 5 next:
2 3 5 7 11 13 17 19 23 29
The next number in the sequence (7) is greater than the square root of N, so we can stop there. The numbers that are left are our prime numbers.
To write your program, use a 1-D array of booleans - one element for each integer up to N. Set them all to true to begin with, but each time you delete an integer, set the corresponding array element to false. The array indices of the true values that are left at the end correspond to the prime numbers.
------解决思路----------------------
public class Test {
private static int length = 29;
public static void main(String[] args) {
int[] array = new int[length];
for(int i=0;i<length;i++){
array[i] = i+2;
}
int index = 0;
while(index != length-1){
for(int i=index;i<length-1;i++){
if(0 == (array[i+1]%array[index])){
int temp=i+1;
while(temp<length-1){
array[temp]=array[temp+1];
temp++;
}
length--;
}
}
index++;
}
for(int i=0;i<length;i++){
System.out.print(array[i]+",");
}
System.out.println();
}
}
------解决思路----------------------
先简单说明一下思路：
1.我构造了一个长度为N+1的布尔型数组并把它们全部置为true（其实不用这样做的，在这里只是为了好看）
2.从2开始一直到srqt(N) 依次累加加上自己，并把得到的数所对应的布尔数组的值置为false
3.把布尔值仍为true的下标打印出来。
有两个比较巧的地方：
1.我们只需要从2 一直试到 sqrt(N) 就可以了
2.如果所选下标对应的布尔值已经为false就没有必要在继续对它进行累加操作了
import java.util.Scanner;
public class PrimeNumberFinder {
public static void main(String [] args){
System.out.println("entry the range of prime number form 1 to ?");
Scanner in=new Scanner(System.in);
int n=in.nextInt();
boolean primeNum[] = new boolean [n+1];
for(int i=2;i<=n;i++)
primeNum[i]=true;
int cout=(int) Math.sqrt(n);
for(int i=2;i<cout;i++){
int j=i;
if(primeNum[j]==true)
do{
j+=i;
if(j<=n)
primeNum[j]=false;
}while(j<n);
}
for(int i=2;i<=n;i++)
if(primeNum[i]==true)
System.out.print(i+" ");
}
}
补充：
1.题主可以参考一下这篇文章求质数算法的N种境界
2.太久没有写java了，所以代码有点丑，请不要介意
3.这个问题还是比较容易的，如果可能的话还是请自己线动一下笔
并祝好
R
------解决思路----------------------
#include <stdio.h>
#include <math.h>
int main(void)
{
int i;
int j;
int a[101]; // 为直观表示，各元素与下标对应，0号元素不用
for (i = 1; i <= 100; i++) // 数组各元素赋值
a[i] = i;
for (i = 2; i < sqrt(100); i++) // 外循环使i作为除数
for (j = i + 1; j <= 100; j++) // 内循环检测除数i之后的数是否为i的倍数
{
if (a[i] != 0 && a[j] != 0) // 排除0值元素
if (a[j] % a[i] == 0)
a[j] = 0; // i后数若为i的倍数，刚将其置0(挖去)
}
int n = 0; // 对输出素数计数, 以控制换行显示
for (i = 2; i <= 100; i++) // 输出素数
{
if (a[i] != 0)
{
printf("%-5d", a[i]); // 输出数组中非0元素(未挖去的数)
n++;
}
if (n == 10)
{
printf("\n"); // 每行10个输出
n = 0;
}
}
printf("\n");
return 0;
}