728x90
1 2 차이가 모더라;; 2가 젤빠르고
int[] 가 ArrayList랑 소요시간 비슷하나 더빠름. 메모리는 ArrayList가 낫겠지..?
첫번째 int array이용
public class PrimeNumber {
public static void main(String[] args) {
// 1. int array
long l1 = System.currentTimeMillis();
int[] a = new int[500];
int index = 0; // prime length
// 1 ~ < 1000
for (int i = 2; i < 1000; i++) {
// 나누기 2~i-1
boolean prime = true;
// / prime
for (int j = 2; j < i; j++) {
// i /
System.out.println(i + " " + j);
if (i % j == 0) {
prime = false;
}
}
if (prime) {
a[index++] = i;
}
}
long l2 = System.currentTimeMillis();
System.out.println("걸린시간="+ (l2-l1)); // 걸린시간=1043
System.out.println(index); // 168
/* foreach로 찍으면 빈공간도 다찍힘 ㄷㄷㄷ
for (int i : a) {
System.out.print(i + " ");
}
*/
for (int i = 0; i < index; i++) {
System.out.print(a[i] + " ");
}
}
}
2번째 int[]
public class PrimeNumber2 {
public static void main(String[] args) {
long l1 = System.currentTimeMillis();
int[] a = new int[5000];
int index = 0; // prime length
// 1 ~ < 1000
// 첫번째 2를 넣고 시작
a[index++] = 2;
// index = 1
for (int i = 3; i < 10000; i++) {
// 나누기 2~i-1
boolean prime = true;
// prime
// 0 ~ index-1
//for (int j = 0; j < index; j++) { // 100:22 1000:185
for (int j = 0; j < index && i/2 >= a[j]; j++) { // 100:18 1000:83
// i /
System.out.println(i + " " + a[j]);
if (i % a[j] == 0) {
prime = false;
break;
}
}
if (prime) {
a[index++] = i;
}
}
long l2 = System.currentTimeMillis();
System.out.println("걸린시간="+ (l2-l1)); // 267 > break 94 > 반 80 169
System.out.println(index); // 168
for (int i = 0; i < index; i++) {
System.out.print(a[i] + " ");
}
}
}
3번째 ArrayList 사용
import java.util.ArrayList;
public class PrimeNumberArray {
public static void main(String[] args) {
long l1 = System.currentTimeMillis();
ArrayList<Integer> a = new ArrayList<Integer>();
// 1 ~ < 1000
// 첫번째 2를 넣고 시작
//a[index++] = 2;
a.add(2);
// index = 1
for (int i = 3; i < 10000; i++) {
// 나누기 2~i-1
boolean prime = true;
// prime
// 0 ~ index-1
//for (int j = 0; j < index; j++) { // 100:22 1000:185
for (int j = 0; j < a.size() && i/2 >= a.get(j); j++) { // 100:18 1000:83
// i /
System.out.println(i + " " + a.get(j));
if (i % a.get(j) == 0) {
prime = false;
break;
}
}
if (prime) {
//a[index++] = i;
a.add(i);
}
}
long l2 = System.currentTimeMillis();
System.out.println("걸린시간="+ (l2-l1)); // 267 > break 94 > 반 80 169
System.out.println(a.size()); // 168
for (int i = 0; i < a.size(); i++) {
System.out.print(a.get(i) + " ");
}
}
}728x90