Модераторы: Daevaorn

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Напечать первые 50 простых чисел, Срочно, помогите! 
:(
    Опции темы
sergejzr
Дата 14.12.2004, 23:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Un salsero
Group Icon


Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 19
Всего: 360
Цитата(LuckLess @ 14.12.2004, 21:30)
for (i=3;i*i<=a;i+=2){

А почему бы сперва не вырешать b=sqrt(a) и решать: for (i=3;i<=b;i+=2) ?



--------------------
Me.
FB.
LinkedIn.
ORCID.
YT.
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
LuckLess
Дата 15.12.2004, 13:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 180
Регистрация: 15.9.2004

Репутация: 1
Всего: 1
sergej.z
Код

int simp(int a){
int i;
if (a<4) return 1;
if (a%2==0) return 0;
for (i=3;i*i<=a;i+=2){
if (a%i==0) return 0;
}
return 1;
}

int simp1(int a){
int i,b;
if (a<4) return 1;
if (a%2==0) return 0;
b=sqrt(a);
for (i=3;i<=b;i+=2){
if (a%i==0) return 0;
}
return 1;
}

void main(void){
int i,j=0,k;
INT64 tm1,tm2,tm;     //dly podscheta zaderzki.
double time;
void *func[]={simp,simp1,NULL};
QueryPerformanceFrequency(&tm); //chastota schetchika v tm
for (k=0;func[k]!=NULL;k++){
i=0;
j=0;
QueryPerformanceCounter(&tm1);//znachenie schetchika v tm1
for(i=1;j<150000;i++){
 if (((int(*)(int))func[k])(i)) j++;
}
QueryPerformanceCounter(&tm2);//znachenie schetchika v tm2;
time=((double)(tm2-tm1))/((double)tm);//podschet pinga.
printf("f-siya N%d : %g  , last val = %d\n",k,time,i-1);
}
_getche();
}


simp1() медленнее simp()
У меня simp() заканчивает за 1.57 секунды , а simp1() за 2.65
PM MAIL   Вверх
LuckLess
Дата 15.12.2004, 14:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 180
Регистрация: 15.9.2004

Репутация: 1
Всего: 1
Думаю связано это с тем , что каждое 3-е число делиться на 3 , поэтому для каждого 3-го числа производится только вычисление 3*3 , а если использовать sqrt , то для всех чисел считаеться кв. корень ..
а кто знает , может sqrt медленнее чем 3*3 и 5*5 вместе , тогда для каждого пятого (за исключением каждого третьего каждого пятого который делиться на 3(каждого 15-го т.е.)) 3*3 и 5*5 выполняется быстрее чем sqrt , и есть еще 7.. и т.д...
PM MAIL   Вверх
sergejzr
Дата 15.12.2004, 16:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Un salsero
Group Icon


Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 19
Всего: 360
Для маленьких чисел получается не выгодно расчитывать корень.
Выгодно для больших, где количество итераций и соотв. выпадающих умножений i*i возмещает затраты на вычисления корня...


--------------------
Me.
FB.
LinkedIn.
ORCID.
YT.
PM WWW IM ICQ Skype GTalk Jabber AOL YIM MSN   Вверх
LuckLess
Дата 15.12.2004, 17:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 180
Регистрация: 15.9.2004

Репутация: 1
Всего: 1
sergej.z
для первых 150,000 чисел , как я говорил simp() была быстрее simp1() в 1.71 раз.
для первых 1,500,000 в 1.66 раз быстрее , представляешь какими громадными должны быть числа , чтобы simp1() стала быстрее..
счаз пойду в агазин , заставлю его первые 5,000,000 чисел найти..
PM MAIL   Вверх
LuckLess
Дата 15.12.2004, 17:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 180
Регистрация: 15.9.2004

Репутация: 1
Всего: 1
хмм.. видимо для 150.000 я не правильно пощитал(слишком округлил) , т.к. для 5,000,000
это соотношение тоже 1,66 (514 и 308 сек соответственно).
PM MAIL   Вверх
maxim1000
Дата 15.12.2004, 17:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 17
Всего: 110
есть еще такое соображение:
достаточно проверять не делимость числа на все предыдущие (ну или до корня), а на все простые, меньшие корня
это не очень хорошо использовать для проверки отдельно взятого числа на простоту, но если уж происходит поиск всех простых чисел, то можно выиграть в скорости...
Код

void qqq(int count)
{
 unsigned int *Primes=new unsigned int[count];
 int PrimesCount;
 int x;

 Primes[0]=2;
 PrimesCount=1;
 x=3;
 while(PrimesCount<n)
 {
   int c;
   bool prime;
   prime=true;
   for(c=0;c<PrimesCount;c++)
   {
     if((x%Primes[c])==0)
     {
       prime=false;
       break;
     }
   }
   if(prime)
     Primes[PrimesCount++]=x;
   x+=2;
 }
 //print ...
}



--------------------
qqq
PM WWW   Вверх
LuckLess
Дата 15.12.2004, 17:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 180
Регистрация: 15.9.2004

Репутация: 1
Всего: 1
перепроверил для 150,000 , поличилось 1,688 (2.55 и 1.51 соответственно).
Не увеличивается видимо изза того , что чем больше числа , тем меньше простых чисел .
А подщет корня дает заметный выигрыш только на них .. а на каждом третьем , 5-ом и т.д.(до какогото прост. яисла) , дает заметный проигрышь.
PM MAIL   Вверх
maxim1000
Дата 15.12.2004, 17:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 17
Всего: 110
только я это не проверял smile
правда, тут проверяются все простые числа меньшие исследуемого
для того, чтобы проверять все простые числа, меньшие корня, можно сделать массив квадратов простых чисел и сравнивать их с числом...


--------------------
qqq
PM WWW   Вверх
LuckLess
Дата 15.12.2004, 17:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 180
Регистрация: 15.9.2004

Репутация: 1
Всего: 1
maxim1000
у тебя 666 сообщений smile smile
Сдесь функции , которые именно проверяют число на простоту , а выводиться какойто диапазон , только , чтобы проверить ее скорость.

И потом , сколько же это будет жрать памяти....
и не факт , что быстрее выйдет..
PM MAIL   Вверх
maxim1000
Дата 15.12.2004, 18:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 17
Всего: 110
Цитата
у тебя 666 сообщений

поздно, уже 667... ой, нет, 668 smile
Цитата
Сдесь функции , которые именно проверяют число на простоту , а выводиться какойто диапазон , только , чтобы проверить ее скорость.

ну не знаю, в заголовке темы написано "первые 50 простых чисел" smile
простые числа встречаются все реже и реже по мере увеличения правой границы диапазона, так что время проверок будет расти медленнее...


--------------------
qqq
PM WWW   Вверх
LuckLess
Дата 15.12.2004, 18:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 180
Регистрация: 15.9.2004

Репутация: 1
Всего: 1
maxim1000
Идея супер. Работает реально быстрее.
Есть идеи по оптимизации моей реализации твоей идеи(см функ. simp2())??
Код

int simp(int a){
int i;
if (a<4) return 1;
if (a%2==0) return 0;
for (i=3;i*i<=a;i+=2){
if (a%i==0) return 0;
}
return 1;
}

int simp1(int a){
int i,b;
if (a<4) return 1;
if (a%2==0) return 0;
b=sqrt(a);
for (i=3;i<=b;i+=2){
if (a%i==0) return 0;
}
return 1;
}


int simp2(int a){
int i;
static int h;
static int *primes;
if (primes==NULL){
primes=(int *)VirtualAlloc(NULL,5000000,MEM_RESERVE|MEM_COMMIT,PAGE_READWRITE);
memset(primes,0,5000000);
primes[0]=3;
}
if (a<4) return 1;
if (a%2==0) return 0;
for (i=0;primes[i]*primes[i]<=a;i++){
if (a%primes[i]==0) return 0;
}
primes[++h]=a;
return 1;
}

void main(void){
int i,j=0,k;
INT64 tm1,tm2,tm;     //dly podscheta zaderzki.
double time;
void *func[]={simp,simp1,simp2,NULL};

QueryPerformanceFrequency(&tm); //chastota schetchika v tm



for (k=0;func[k]!=NULL;k++){
i=0;
j=0;
QueryPerformanceCounter(&tm1);//znachenie schetchika v tm1
for(i=1;j<100000;i++){
 if (((int(*)(int))func[k])(i)) j++;
}
QueryPerformanceCounter(&tm2);//znachenie schetchika v tm2;
time=((double)(tm2-tm1))/((double)tm);//podschet pinga.
printf("f-siya N%d : %g  , last val = %d\n",k,time,i-1);

}

_getche();
}

Добавлено @ 19:00
функция simp() справилась с 1.000.000 числами за 26 сек , а simp2() за 8 сек!
PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0771 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.