private static int n = 21474;
private static int m = 20000;
Все равно вылетает вот такая ошибочка
Exception in thread "main" java.lang.ArithmeticException: / by zero
at algorithmen2_1.Algorithmen2_1.main(Algorithmen2_1.java:35)
Java Result: 1
BUILD SUCCESSFUL (total time: 1 second)
Простые числа от 2000000000 до INT_MAX, Как, чтоб не загнать оперативку?
Здравствуйте, поступила задача. В принципе все кажется просто, найти простые числа в заданном диапазоне.
Но диапазон слишком большой и нужно учитывать память, тоисть по идее массив использовать не получится. Пересмотрели варианты, наиболее подходитРешето Эратосфена - но в нем используется массив, что мы себе позволить не можем из-за оперативки. А... и пройти он должен менее чем за 3 минуты.
Подскажите в какую сторону смотреть с решением, спасибо.
Но диапазон слишком большой и нужно учитывать память, тоисть по идее массив использовать не получится. Пересмотрели варианты, наиболее подходитРешето Эратосфена - но в нем используется массив, что мы себе позволить не можем из-за оперативки. А... и пройти он должен менее чем за 3 минуты.
Подскажите в какую сторону смотреть с решением, спасибо.
И при чём здесь оперативка? Память кучи хорошо защищена. Используйте массив смело, проблемы начнутся только если он у вас больше 2Gb будет, но думаю до этого не дойдет. И работать будет быстро. Для адресации более 2Gb см. статьи по AWE для 32 разрядных систем.
Господа, делаю вот так, вылетает на строчке int h = m % primes; после 54 секунды просчетов.
что не так? Подскажете? Спасибо.
ЯваКод
что не так? Подскажете? Спасибо.
ЯваКод
Код:
package algorithmen2_1;
import java.util.Arrays;
public class Algorithmen2_1 {
private static int n = 2147483647;
private static int m = 2000000000;
public static void main(String[] args) {
int z = (int) Math.sqrt((double) n);
int[] primes = new int[z];
for(int i=2;i<=z;i++)
primes[i-2]=i;
boolean[] sieve = new boolean[n - m + 1];
Arrays.fill(sieve, true);
for (int i = 0; i < z; i++) {
int h = m % primes;
int j = h == 0 ? 0 : primes - h;
for (; j <= n - m; j += primes) {
sieve[j] = false;
}
}
}
}
import java.util.Arrays;
public class Algorithmen2_1 {
private static int n = 2147483647;
private static int m = 2000000000;
public static void main(String[] args) {
int z = (int) Math.sqrt((double) n);
int[] primes = new int[z];
for(int i=2;i<=z;i++)
primes[i-2]=i;
boolean[] sieve = new boolean[n - m + 1];
Arrays.fill(sieve, true);
for (int i = 0; i < z; i++) {
int h = m % primes;
int j = h == 0 ? 0 : primes - h;
for (; j <= n - m; j += primes) {
sieve[j] = false;
}
}
}
}
С каким исключением вылетает?
Господа, уже не вылетает, по скромным подсчетам эта выборка будет делаться 12.5 часов, а нам нужно за 3 минуты максимум, как можно оптимизировать? Спасибо.
Как расчитывали время?
В последнем цыкле засекли время прохождения 1 милиона получилось 45 секунд, итого 2 милиарда 12.5 часов. :(
Как расчитывали время?
В последнем цыкле засекли время прохождения 1 милиона получилось 45 секунд, итого 2 милиарда 12.5 часов. :(
Цитата: webdev
Господа, уже не вылетает, по скромным подсчетам эта выборка будет делаться 12.5 часов, а нам нужно за 3 минуты максимум, как можно оптимизировать? Спасибо.
Как расчитывали время?
В последнем цыкле засекли время прохождения 1 милиона получилось 45 секунд, итого 2 милиарда 12.5 часов. :(
Как расчитывали время?
В последнем цыкле засекли время прохождения 1 милиона получилось 45 секунд, итого 2 милиарда 12.5 часов. :(
А подсчитать заранее эти простые числа, а потом дёргать их из файла не вариант? Они же меняться не будут никогда, так зачем их пересчитывать каждый раз?
Хммм, уже предлагали такое решение, я согласен, что это более разумный вариант, но боюсь преподу который ведет Алгоритмы такой подход не понравится. :(
Неужели никто в своей практике с таким не сталкивался? :( О Числах и миллионах, примеров полно и все разжовано, а вот такой диапазон...
У кого какие еще соображения? Спасибо.
Неужели никто в своей практике с таким не сталкивался? :( О Числах и миллионах, примеров полно и все разжовано, а вот такой диапазон...
У кого какие еще соображения? Спасибо.
загоните в таблицу все простые число ДО 2000000000 . не думаю что это запрещено . )
а отсеивание лучше методом эратосфена делать - помечать не простые числа и больше не использовать .
а отсеивание лучше методом эратосфена делать - помечать не простые числа и больше не использовать .
Что вы имеете введу под "загоните в таблицу все простые число ДО 2000000000" - если вы имеете введу взять готовые, то этот вариант отпадает, поскольку нам их нужно найти, если вы к этому под таблицей имеете введу массив, то при попытке создать такой массив ява скажет что у нее heap слишком маленький.
Вот два варианта (правда на c++ но алгоритм поймёшь): 1-й работает примерно 20 сек он отсеивает из диапазона [2000000001,INT_MAX] все непростые числа. 2-й работает медленно (примерно 4-е минуты) он последовательно проверяет все числа из нужного диапазона. (Время для пенька4 @2.3GHz stdout перенаправлен в файл) По оперативе 1-й вариант примерно 650 мб занимает 2-й - совсем немного, т.к. большого массива не создаётся.
1)
2)
1)
Код:
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <limits.h>
int main(){
time_t rawtime;
struct tm * timeinfo;
time ( &rawtime );
timeinfo = localtime ( &rawtime );
printf ( "Запущен : %s", asctime (timeinfo) );
//=============================================
unsigned int size1=sqrt(INT_MAX);
unsigned int *firstarr=new unsigned int[size1];
firstarr[0]=2;
for(unsigned int a = 1;a<size1;a+=1)
firstarr[a]=a+2;
unsigned int size2=sqrt(size1)+1;
for(unsigned int a = 0;a<size2;a+=1)
{
if(firstarr[a]!=0)
for(unsigned int b=a+1;b<size1;b+=1)
if(firstarr!=0)
if(firstarr%firstarr[a]==0)
firstarr=0;
}
unsigned int count1=0;
for(unsigned int a=0;a<size1;a+=1)
if(firstarr[a]!=0)
count1+=1;
printf("%d\n",count1);
time ( &rawtime );
timeinfo = localtime ( &rawtime );
printf ( "Нашли все простые до корня из INT_MAX : %s", asctime (timeinfo) );
size2=INT_MAX-2000000000;
unsigned int * secondarr=new unsigned int[size2];
for(unsigned int a = 0; a <size2;a+=1)
secondarr[a]=a+2000000001;
printf ( "Заполнили второй массив размером %d : %s",size2 , asctime (timeinfo) );
for(unsigned int a = 0;a<size1;a+=1)
{
if(firstarr[a])
{
unsigned int tmp=firstarr[a]*(2000000001/firstarr[a]);
if(tmp<2000000001)
tmp+=firstarr[a];
while(tmp<=INT_MAX)
{
secondarr[tmp-2000000001]=0;
tmp+=firstarr[a];
}
}
}
unsigned int primes=0;
for(unsigned int a=0;a<size2;a+=1)
if(secondarr[a]!=0)
{
printf("%d\n",secondarr[a]);
primes+=1;
}
printf("Primes: %d\n",primes);
//=============================================
time ( &rawtime );
timeinfo = localtime ( &rawtime );
printf ( "Закончили : %s", asctime (timeinfo) );
return 0;
}
#include <math.h>
#include <time.h>
#include <limits.h>
int main(){
time_t rawtime;
struct tm * timeinfo;
time ( &rawtime );
timeinfo = localtime ( &rawtime );
printf ( "Запущен : %s", asctime (timeinfo) );
//=============================================
unsigned int size1=sqrt(INT_MAX);
unsigned int *firstarr=new unsigned int[size1];
firstarr[0]=2;
for(unsigned int a = 1;a<size1;a+=1)
firstarr[a]=a+2;
unsigned int size2=sqrt(size1)+1;
for(unsigned int a = 0;a<size2;a+=1)
{
if(firstarr[a]!=0)
for(unsigned int b=a+1;b<size1;b+=1)
if(firstarr!=0)
if(firstarr%firstarr[a]==0)
firstarr=0;
}
unsigned int count1=0;
for(unsigned int a=0;a<size1;a+=1)
if(firstarr[a]!=0)
count1+=1;
printf("%d\n",count1);
time ( &rawtime );
timeinfo = localtime ( &rawtime );
printf ( "Нашли все простые до корня из INT_MAX : %s", asctime (timeinfo) );
size2=INT_MAX-2000000000;
unsigned int * secondarr=new unsigned int[size2];
for(unsigned int a = 0; a <size2;a+=1)
secondarr[a]=a+2000000001;
printf ( "Заполнили второй массив размером %d : %s",size2 , asctime (timeinfo) );
for(unsigned int a = 0;a<size1;a+=1)
{
if(firstarr[a])
{
unsigned int tmp=firstarr[a]*(2000000001/firstarr[a]);
if(tmp<2000000001)
tmp+=firstarr[a];
while(tmp<=INT_MAX)
{
secondarr[tmp-2000000001]=0;
tmp+=firstarr[a];
}
}
}
unsigned int primes=0;
for(unsigned int a=0;a<size2;a+=1)
if(secondarr[a]!=0)
{
printf("%d\n",secondarr[a]);
primes+=1;
}
printf("Primes: %d\n",primes);
//=============================================
time ( &rawtime );
timeinfo = localtime ( &rawtime );
printf ( "Закончили : %s", asctime (timeinfo) );
return 0;
}
2)
Код:
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <limits.h>
int main(){
time_t rawtime;
struct tm * timeinfo;
time ( &rawtime );
timeinfo = localtime ( &rawtime );
printf ( "Запущен : %s", asctime (timeinfo) );
//===============================================
unsigned int *primes=new unsigned int[10000000];
unsigned int count=1;
primes[0]=2;
bool prime;
unsigned int stop;
unsigned int sqr=sqrt(INT_MAX);
for(unsigned int i=3;i<sqr;i+=2)
{
prime=true;
stop=sqrt(i);
for(unsigned int j=1;j<count;j+=1)
{
if(primes[j]>stop)
break;
if(i%primes[j]==0)
{
prime=false;
break;
}
}
if(prime)
{
primes[count]=i;
count+=1;
}
}
printf("%d\n",count);
time ( &rawtime );
timeinfo = localtime ( &rawtime );
printf ( "Нашли все до %d: %s",sqr, asctime (timeinfo) );
unsigned int count2=0;
for(unsigned int i=2000000001;i<=INT_MAX;i+=2)
{
prime=true;
for(unsigned int j=1;j<count;j+=1)
{
if(i%primes[j]==0)
{
prime=false;
break;
}
}
if(prime)
{
count2+=1;
printf("%d\n",i);
}
}
printf("Primes: %d\n",count2);
//===============================================
time ( &rawtime );
timeinfo = localtime ( &rawtime );
printf ( "Закончили : %s", asctime (timeinfo) );
return 0;
}
#include <math.h>
#include <time.h>
#include <limits.h>
int main(){
time_t rawtime;
struct tm * timeinfo;
time ( &rawtime );
timeinfo = localtime ( &rawtime );
printf ( "Запущен : %s", asctime (timeinfo) );
//===============================================
unsigned int *primes=new unsigned int[10000000];
unsigned int count=1;
primes[0]=2;
bool prime;
unsigned int stop;
unsigned int sqr=sqrt(INT_MAX);
for(unsigned int i=3;i<sqr;i+=2)
{
prime=true;
stop=sqrt(i);
for(unsigned int j=1;j<count;j+=1)
{
if(primes[j]>stop)
break;
if(i%primes[j]==0)
{
prime=false;
break;
}
}
if(prime)
{
primes[count]=i;
count+=1;
}
}
printf("%d\n",count);
time ( &rawtime );
timeinfo = localtime ( &rawtime );
printf ( "Нашли все до %d: %s",sqr, asctime (timeinfo) );
unsigned int count2=0;
for(unsigned int i=2000000001;i<=INT_MAX;i+=2)
{
prime=true;
for(unsigned int j=1;j<count;j+=1)
{
if(i%primes[j]==0)
{
prime=false;
break;
}
}
if(prime)
{
count2+=1;
printf("%d\n",i);
}
}
printf("Primes: %d\n",count2);
//===============================================
time ( &rawtime );
timeinfo = localtime ( &rawtime );
printf ( "Закончили : %s", asctime (timeinfo) );
return 0;
}