There are four code snippets
The first is the most basic method. Because the efficiency of the method is too poor, it is tested with 10W first. The final optimized program will run all prime numbers within 100W. Because the program has different thinking and computing power, there will be an episode in the middle, which will be explained in the third and fourth codes
The first code segment is the most basic algorithm: the number and time of prime numbers within 10W (at the same time, the results of this code are used to compare the output correctness of the optimized code)
Program running time: 7441ms
Number of prime numbers: 9592
package cn.king;
public class test1 {
public static void main(String[] args) {
int k =0;
long startTime = System.currentTimeMillis() ; //Get start time
for(int i=2;i<=100000;i++) {
boolean t = true;
for(int j=2;j<i;j++) {
if(i%j==0) {
t=false;
}
}
if(t==true) {
System.out.println(i);
k++;
}
}
long endTime = System.currentTimeMillis() ; //Get end time
System.out.println("Program run time:" + (endTime - startTime) + "ms");
System.out.println("Prime number:"+k);
}
}
For the second optimized code, the time complexity of this optimization is o(n), so the effect will be much worse when the number is high. Later, it will be compared when the prime number is within 100W. After comparison, it can be found that there is no problem in the number. This optimization is successful There is a lot less time
Program running time: 384ms
Number of prime numbers: 9592
package cn.king;
public class test2 {
public static void main(String[] args) {
int k =0;
long startTime = System.currentTimeMillis() ; //Get start time
for(int i=2;i<=100000;i++) {
boolean t = true;
for(int j=2;j<=i/2;j++) {
if(i%j==0) {
t=false;
break;
}
}
if(t==true) {
System.out.println(i);
k++;
}
}
long endTime = System.currentTimeMillis() ; //Get end time
System.out.println("Program run time:" + (endTime - startTime) + "ms");
System.out.println("Prime number:"+k);
}
}
Next, the third optimization, which is also the most recommended optimization, (Note: Math.sqrt(i) means to open the root), has changed its time complexity to the root n. however, when the amount of data is small, such as 100, the efficiency including the fourth optimization will not be as good as the second optimization, because it takes a long time to open the square, so it will be better when the data is large
Compared with the above, the number is the same
Program running time: 51ms
Number of prime numbers: 9592
package cn.king;
public class test1 {
public static void main(String[] args) {
boolean t ;
int k =0;
long startTime = System.currentTimeMillis() ; //Get start time
for(int i=2;i<=100000;i++) {
t = true;
for(int j=2;j<=(int) Math.sqrt(i);j++) {
if(i%j==0) {
t=false;
break;
}
}
if(t==true) {
System.out.println(i);
k++;
}
}
long endTime =System.currentTimeMillis() ; //Get end time
System.out.println("Program run time:" + (endTime - startTime) + "ms");
System.out.println("Prime number:"+k);
}
}
The fourth method involves some mathematical knowledge. It uses data to remove the previous prime number, and then writes the obtained prime number into the array. In the calculation of human brain, this method will be simpler than the above, but in machine language, the speed of this method will be lower than that of the third method because of different efficiency in processing different data and amplification,
Compared with the above, the number is the same
Program running time: 136ms
Number of prime numbers: 9592
package cn.king;
import java.util.Arrays;
public class test3 {
static boolean t;
static int k =0;
static int size=1;
public static void main(String[] args) {
int[] a= {2};
long startTime = System.currentTimeMillis() ;
for(int l=0;l<a.length;l++) {
System.out.println(a[l]);
k++;
}
for(int i=2;i<100000;i++) {
t=true;
for(int j=0;j<size;j++) {
if(i%a[j]==0) {
t=false;
break;
}
}
if(t==true) {
a=Arrays.copyOf(a,++size);
a[size-1]=i;
System.out.println(i);
k++;
}
}
long endTime = System.currentTimeMillis(); //Get end time
System.out.println("Program run time:" + (endTime - startTime) + "ms");
System.out.println("Prime number:"+k);
}
}
Next, the comparison within 100W will be carried out. Because the speed of method 1 is too slow, it will be eliminated (stone hammer tool man)
Method 2: program running time: 28846ms; prime number: 78498
Method 3: program running time: 601ms # prime number: 78498
Method 4: program running time: 5881ms # prime number: 78498
It can be found that the time gap at this time is very different, and the efficiency gap between method 3 and method 2 is nearly 50 times If the amount of data is larger, there will be more gaps So it shows the necessity of code optimization
Next, the comparison within 1000W will be carried out, because the speed of method 2 is too slow and is eliminated (afraid of running to the end of time)
Method 3: program running time: 11915s # prime number: 664579
Method 4: program running time: 463325ms; number of prime numbers: 664579
It can be seen that the efficiency gap between method 3 and method 4 is nearly 50 times The efficiency of method 3 is much higher than that of method 4
The next is the ultimate challenge. The time and number of methods within 100 million will also be eliminated (afraid of the computer running and exploding in place)
Method 3: the last prime number within 100 million is 9999989. Program running time: 333806ms. Prime number: 5761455
It can be found that the time spent running prime numbers less than 100 million with method 3 is faster than that running prime numbers less than 10 million with method 4
To sum up, method 3 conforms to Wang Jingze Zhenxiang's theorem