Форум C++

Всем доброго времени суток.
Где-то на сайте вроде бы видел похожие темы, но к сожалению на даный момент нет времени сильно глубоко копать, если вас не затруднит помогите бедному студенту )).
В общем есть задача:
- Напишите на языке Си программу, определяющую, является ли введеное пользователем натуральное число простым ( Объясните пожалуйста алгоритм проверки числа на "простоту" ).

#include <stdio.h> #include <conio.h> int num, pr; void main() {  puts("Введите натуральное число - ");  scanf("%d", &num);  if(num<0)   printf("Число \"%d\" не натуральное", num);  else  {   pr=num%2;/* Принимаем за делитель для проверки минимальное простое чило*/   if(pr)   printf("Число \"%d\" является простым.", num);   else   printf("Число \"%d\" не является простым.", num);  }  puts("Для закрытия нажмите любую клавишу");  getch(); }

с одной стороны вроде бы как и работает (по крайней мере при малых значениях), а с другой стороны как-то слишком просто (((.

Вы проверяете число на четность.
Вот такая проверка простое/составное:

if ( (num % 2) != 0 ) // если число нечетное, иначе оно составное {  for(int i = 3; i < num / 2; i++)   // имеет смысл искатьделители только среди чисел, меньших num/2  {   if ( (num % i) == 0 )   {    // число простое - найден делитель i   }  } }

Более того, имеет смысл искать делители только меньше корня квадратного из num!

А пример не могли бы привести.
Вообще-то преподаватель разрешила и просто тупо в цикле с шагом 1 прогнать поиск делителя, но для себя интересно просто разные варианты по сравнивать(единственный предмет который буду сам сдавать и интересен на 1 курсе).

Вот, можете сравнить производительность:

#include <math.h> #include <stdio.h> #include <windows.h> inline bool isSimple1(long num) {  if ( (num % 2) != 0)  {   for(int i = 0; i < (num / 2); i++)   {    if ( (num % i) == 0)    {     return false;    }   }   return true;  }  return false; } inline bool isSimple2(long num) {  if ( (num % 2) != 0)  {   for(int i = 0; i < sqrt(num); i++)   {    if ( (num % i) == 0)    {     return false;    }   }   return true;  }  return true; } int main() {  DWORD dwTime = GetTickCount();    for(int i = 0; i < 200000000; i++)  {   isSimple1( rand() / RAND_MAX * 2000000000 );  }  printf("Метод с делением пополам: %d мс\n", GetTickCount() - dwTime);    dwTime = GetTickCount();  for(int i = 0; i < 200000000; i++)  {   isSimple2( rand() / RAND_MAX * 2000000000 );  }  printf("Метод с квадратным корнем: %d мс\n", GetTickCount() - dwTime);    scanf("\n");  return 0; }

Эээ, нет батенька не все так просто!

for(int i = 0; i < sqrt(num); i++) { }

зачем дофига раз считать квадратный корень???

лучше вот так:

int temp=sqrt(num); for(int i = 0; i < temp; i++) { }

Корень быстрее. Ибо проверок меньше будет.

Хех, понадеялся на автооптимизацию - а зря! Получается выигрыш примерно на 90-110 мс.
Кстати, что странно - у меня в 2 случаях из 3 побеждает вервый вариант с разницей в 200-300 мс, а вот в оставшемся случае - второй, причем с разницей почти в секунду. Интересно, почему?

Хм..
я думаю, при малых числах, выигрывает первый вариант, где без корня,
так как проверок там не сильно больше, чем в варианте с корнем.
то есть цикл выполняется примерно одинаковое число раз при малых числах.
но во втором варианте мы еще считаем один раз корень! а это ресурсоемкая операция.

попробуйте проверить отдельно на малых и больших числах.

Всем спасибо, только после того как сдал контрольную с вариантом sqrt мне усложнили задачу, что бы не умничал ((
http://www.softtime.ru/cpp/read.php?id_forum=1&id_theme=676