من اینو با #C نوشته بودم و برپایه‌ی غربال اراتستن. البته به نظرم خیلی میشه از این بیشتر بهینه سازیش کرد... مثلا اگه برای یه تعداد معلوم ولی زیاد نیاز داریش اگه به جای ArrayList از یه آرایه استفاده کنی مطمئنا خیلی تو سرعتش تاثیر داره. یا مثلا برای تعداد خیلی زیاد شاید بشه گام‌های حلقه رو برای اعداد اول بزرگتر از ۱۰۰ تغییر داد تا سرعت زیاد شه ولی اعداد اول دو قلو رو پیدا نکنه و از این کارا!
public static ArrayList<Integer> getPrimes(int n) {
ArrayList<Integer> primes = new ArrayList<>();
if(n <= 1) {
return primes;
}
primes.add(2);
main_loop: for(int i = 3; i <= n; i += 2) {
for(Integer prime : primes) {
if(i % prime == 0) {
continue main_loop;
}
}
primes.add(i);
}
return primes;
}
روی سیستم من تا ۱۰۰۰۰۰۰ خوب جواب داد نسبتا. ولی اگه وابسته به نیازت یه چیزاییش رو تغییر بدی و مخصوصا اگه با ++C پیاده سازیش کنی بهتر نتیجه میگیری.
public static void main(String[] args) {
ArrayList<Integer> primes = getPrimes(1000000);
try(FileOutputStream fos = new FileOutputStream("primes.list");
PrintWriter pw = new PrintWriter(fos)) {
for(Integer prime : primes) {
pw.println(prime);
}
} catch (IOException ex) {
ex.printStackTrace();
}
}
امیدوارم بت کمک کنه.
پاسخ با نقل قول