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

Поиск:

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


Unregistered
Друзья! У меня такая проблема: надо в обычном С напечатать первые 50 (500) простых чисел. Помогите. Заранее очень благодарю!
  Вверх
Parviz
Дата 11.12.2004, 14:44 (ссылка) | (голосов: 0) Загрузка ... Загрузка ... Быстрая цитата Цитата


Unregistered
Друзья! У меня такая острая проблема: надо в обычном С напечать первые 50 (500) простых чисел. Как мне быть? помогите. Очень спасибо
  Вверх
_hunter
Дата 11.12.2004, 15:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник Клуба
Сообщений: 8564
Регистрация: 24.6.2003
Где: Europe::Ukraine:: Kiev

Репутация: 16
Всего: 98
начинай писать -- а мы поможем.
да и поиском пользоваться не помешает.
http://forum.vingrad.ru/index.php?showtopic=15926


--------------------
Tempora mutantur, et nos mutamur in illis...
PM ICQ   Вверх
LuckLess
Дата 11.12.2004, 15:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

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

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

void main(void){
int i,j=0;
for(i=1;j<10;i++){
if (simp(i)) {
printf("%d:%d\n",++j,i);
}
}
_getche();
}


в строчке for(i=1;j<10;i++) менаешь количество нузних тепе простых чисел

Это сообщение отредактировал(а) LuckLess - 11.12.2004, 16:06
PM MAIL   Вверх
Guest
Дата 11.12.2004, 16:51 (ссылка) | (голосов: 0) Загрузка ... Загрузка ... Быстрая цитата Цитата


Unregistered
спасибо огромное!
  Вверх
Alexandr87
Дата 12.12.2004, 17:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


дыкий псых
***


Профиль
Группа: Завсегдатай
Сообщений: 1459
Регистрация: 27.11.2004
Где: Алматы, Казахстан

Репутация: 2
Всего: 39
LuckLess
Как мне кажется сий код, не будет выводить первые 10 простых чисел, но будет выводить просты числа от 1 до 10
PM Jabber   Вверх
Alexandr87
Дата 12.12.2004, 17:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


дыкий псых
***


Профиль
Группа: Завсегдатай
Сообщений: 1459
Регистрация: 27.11.2004
Где: Алматы, Казахстан

Репутация: 2
Всего: 39
должно быть нечто такого


Код

int kol=2;
int tek=3;
bool prov2;
cout<<"1\t1\n";
cout<<"2\t2\n";
while(kol<50)
{
prov2=0;
for (int x=2; x<tek; x++)
 if (tek%x==0)
  {prov2=1;break;}
if (prov2==0)
 cout<<tek<<"\t"<<++kol<<endl;
tek++;
}


Функции вывода С не знаю сам заменишь

Это сообщение отредактировал(а) Alexandr87 - 12.12.2004, 18:24
PM Jabber   Вверх
LuckLess
Дата 13.12.2004, 00:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

Репутация: 1
Всего: 1
Alexandr87
а ты проверь перед тем как говоритрь smile
Добавлено @ 00:48
Скорее всего ты так подумал изза того что в строчке
for(i=1;j<10;i++){
ты решил что написано I<10 а не J<10 как у меня.

Это сообщение отредактировал(а) LuckLess - 13.12.2004, 00:48
PM MAIL   Вверх
cardinal
Дата 13.12.2004, 01:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Инженер
****


Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 2
Всего: 99
http://forum.vingrad.ru/index.php?showtopic=36021


--------------------
Немецкая оппозиция потребовала упростить натурализацию иммигрантов
В моем блоге: Разные истории из жизни в Германии

"Познание бесконечности требует бесконечного времени, а потому работай не работай - все едино".  А. и Б. Стругацкие
PM   Вверх
azesmcar
Дата 13.12.2004, 09:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


uploading...
****


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

Репутация: 81
Всего: 211
LuckLess
Кстати для того чтоб узнать простое ли число достаточно попытаться разделить его до корня самого числа...
примерно вот так..
Код

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


Немного быстрее получается
PM   Вверх
maxim1000
Дата 13.12.2004, 09:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


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

Репутация: 17
Всего: 110
Цитата
i<=int(sqrt(a))

ну и тогда, чтоб не привлекать сюда арифметику с плавающей запятой:
Код
i*i<=a




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


Бывалый
*


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

Репутация: 1
Всего: 1
Цитата(azesmcar @ 13.12.2004, 09:04)
Немного быстрее получается

Спасибо!! Получться не немного а намного быстрее при больших числах.
PM MAIL   Вверх
cardinal
Дата 14.12.2004, 15:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Инженер
****


Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 2
Всего: 99
А если посмотреть ту ссылку, которую я дал, то можно сделать еще быстрее. Там умножение заменяется на хитрое сложение и лишний раз ничего не проверяется smile


--------------------
Немецкая оппозиция потребовала упростить натурализацию иммигрантов
В моем блоге: Разные истории из жизни в Германии

"Познание бесконечности требует бесконечного времени, а потому работай не работай - все едино".  А. и Б. Стругацкие
PM   Вверх
LuckLess
Дата 14.12.2004, 22:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

Репутация: 1
Всего: 1
cardinal
к сожалению VB не знаю човсем , поетому понять там ничекго не смог.
И , у меня нигде нет умножения чтоб его заменять сложением...


А нащет на сколько быстрее получиться , стало мне интересно , сделал небольшой тест...
Код

#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <sys/types.h>
#include <sys/timeb.h>
#include <basetsd.h>
#include <windows.h>

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;
if (a<4) return 1;
if (a%2==0) return 0;
for (i=3;i<a/2;i+=2){
if (a%i==0) return 0;
}
return 1;
}

int easysimp(int a){
int i;
if (a<4) return 1;
for (i=2;i<a;i++){
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[]={easysimp,simp1,simp,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();
}

Результат ошеломил слегда поначалу...
1-я функция сделала это за 4100 секунд
2-я функция сделала это за 1060 секунд , чего и следовало ожидать..
а 3-я функция сделала это за 2!!!!! секунды.

Вобщем правда потом пощитал на бумажке , и понял , что так по идее и должно было быть..
но сразу глазам не поверилsmile

Это сообщение отредактировал(а) LuckLess - 14.12.2004, 22:33
PM MAIL   Вверх
cardinal
Дата 14.12.2004, 22:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Инженер
****


Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 2
Всего: 99
Цитата(LuckLess @ 14.12.2004, 21:30)
И , у меня нигде нет умножения чтоб его заменять сложением...

Ну деление, без разницы...
Код

if (a%i==0) return 0;

Пока все еще думаю, что можно сделать быстрее smile


--------------------
Немецкая оппозиция потребовала упростить натурализацию иммигрантов
В моем блоге: Разные истории из жизни в Германии

"Познание бесконечности требует бесконечного времени, а потому работай не работай - все едино".  А. и Б. Стругацкие
PM   Вверх
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   Вверх
Страницы: (2) [Все] 1 2 
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
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.0707 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


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

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