число простое или составное

[isus]

как ето можно сделать? просто я 1 вариант предложил преподу ему непонравилось.

[Базиля]

Держи:

program zad1;
var
n:integer;

begin
writeln('введите число');
readln(n);
if (n=2) or (n=3) then writeln('число простое')
else
if  (n mod 2 = 0) or (n mod 3=0) then
writeln('число составное')
else
writeln('простое');
end.

думаю алгоритм моего решения ясен?
если что сразу поясню:
Любое составное число делится на 2 или 3 без остатка, но так как сами эти числа (2 и 3) являются простыми я добавил:

if (n=2) or (n=3) then writeln('число простое')
else

[Kopwyh]

Не знаю какой вариант ты ему предлагал.
1. Перебрать все числа, вплоть до корня из него и поделить с остатком (в си операция выглядит как %, в бейсике и паскале как MOD)
2. Как вариант, забить таблицу простых чисел и прогнать такую же проверку на них.
3. Предложи преподу реализовать Решето Эрастосфена, или http://ru.wikipedia.org/wiki/%D0%A0%...B8%D0%BD%D0%B0
(там, кстати и код есть )

[Alex_FF]

Любое составное число делится на 2 или 3 без остатка, но так как сами эти числа (2 и 3) являются простыми я добавил:

Нет.
49 - составное число, равное произведению 7 * 7, где 7 - простое число.
на 2 и 3 49 не делится
чтобы определить простое число X или нет, нужно проверить делимость этого числа на числа, начиная с 2 до корень квадратный из X. Если найдется такое число из промежутка [2; sqrt(X)], на которое X делится без остатка, то X - составное, иначе - простое.
это вот так записывается (это для натуральных чисел; отрицательные числа - не простые по определению натурального числа):

{ Возвращает TRUE если число простое }
function PrimeNumber(X: Longint): Boolean;
var
  I: Integer;
  F: Boolean;
begin
  F := True;
  for I := 2 to Trunc(Sqrt(X)) do
    if X mod I = 0 then
    begin
      F := False;
      Break;
    end;
  PrimeNumber := F and (X <> 1);
end;

[Базиля]

Нет.
49 - составное число, равное произведению 7 * 7, где 7 - простое число.
на 2 и 3 49 не делится

Если только это число то можно еще одно условие добавить и все))
Ну да ладно, не рационально получается

[Alex_FF]

Сообщение от Базиля

Если только это число то можно еще одно условие добавить и все))
Ну да ладно, не рационально получается

нет, не только. Простые числа составляют бесконечное множество, это еще Евклид доказал.
Произведение любых нескольких простых чисел - число составное.
Например, 65537 - простое число, 17 - тоже простое, 1114129 = 65537 * 17 - составное число.

[isus]

всем спасибо я сделал так! что скажите?
r-вводим

int t=0,k=0;

for( int i=2; i<=r; i++){
if(r%i==0 && r/i==1){

t++;
break;
}
if(r%i==0 && r/i!=1){

k++;
break;
}
}
if(t==1 && k==0){printf("простое\n");}
else{printf("составное\n");}

[Базиля]

isus
я СИ не знаю( И почему нельзя было сразу в первом посте написать, что делать нужно на СИ?

[isus]

Бразилия...я же непросил делать я просил подать идею)

[Alex_FF]

Сообщение от isus

всем спасибо я сделал так! что скажите?
r-вводим

int t=0,k=0;

for( int i=2; i<=r; i++){
if(r%i==0 && r/i==1){

t++;
break;
}
if(r%i==0 && r/i!=1){

k++;
break;
}
}
if(t==1 && k==0){printf("простое\n");}
else{printf("составное\n");}

это плохой алгоритм. Нужно проверять числа от двух, до КОРЕНЬ КВАДРАТНЫЙ ИЗ r.

bool PrimeNumber(long x)
{
	 bool f = true;
	 for (int i = 2; i < floor(sqrt((double)x)); i++)
		  if (x % i == 0)
		  {
			  f = false;
			  break;
		  }
	 return (f && (x != 1));
}