Java implements three methods for finding primes less than n
- 2020-04-01 03:47:38
- OfStack
Prime concept
Prime, also known as the prime, to point to in a is greater than 1 (link: http://zh.wikipedia.org/wiki/%E8%87%AA%E7%84%B6%E6%95%B0), in addition to 1 and the integer itself, cannot be other natural number (link: http://zh.wikipedia.org/wiki/%E6%95%B4%E9%99%A4) number (can also be defined as only 1 and itself two (link: http://zh.wikipedia.org/wiki/%E5%9B%A0%E6%95%B8).
The smallest prime number is 2, is also a prime number, the only (link: http://zh.wikipedia.org/wiki/%E5%81%B6%E6%95%B0); Other prime Numbers are (link: http://zh.wikipedia.org/wiki/%E5%A5%87%E6%95%B0). There are infinitely many primes, so there is no largest prime.
1. Solve according to the definition:
It is also the most stupid way, which is less efficient:
package test.ms;
public class FindPrime {
// find the prime between 1 to 1000;
public static void main(String[] args) {
printPrime(1000);
}
public static void printPrime(int n){
for(int i = 2; i < n ; i++){
int count = 0;
for(int j = 2 ; j<=i; j++){
if(i%j==0){
count++;
}
if(j==i & count == 1){
System.out.print(i+" ");
}
if(count > 1){
break;
}
}
}
}
}
2: square root:
package test.ms;
public class Prime {
public static void main(String[] args) {
for(int j = 2; j<1000; j++){
if(m(j)){
System.out.print(j+" ");
}
}
}
public static boolean m(int num){
for(int j = 2; j<=Math.sqrt(num);j++){
if(num%j == 0){
return false;
}
}
return true;
}
}
3: find a pattern (from a forum discussion)
The smallest prime is 2, which is the only even number of primes; All the other primes are odd. There are infinitely many primes, so there is no largest prime.
package test.ms;
import java.util.ArrayList;
import java.util.List;
public class Primes {
public static void main(String[] args) {
//For prime
List<Integer> primes = getPrimes(1000);
//The output
for (int i = 0; i < primes.size(); i++) {
Integer prime = primes.get(i);
System.out.printf("%8d", prime);
if (i % 10 == 9) {
System.out.println();
}
}
}
private static List<Integer> getPrimes(int n) {
List<Integer> result = new ArrayList<Integer>();
result.add(2);
for (int i = 3; i <= n; i += 2) {
if (!divisible(i, result)) {
result.add(i);
}
}
return result;
}
private static boolean divisible(int n, List<Integer> primes) {
for (Integer prime : primes) {
if (n % prime == 0) {
return true;
}
}
return false;
}
}
The first and second methods are both very simple:
The third method illustrates the property of a prime number: of all primes, only 2 is even.
A number is not prime if it is divisible by its previous prime.