Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 23.09.2014, 21:04   #11
Тетрадь
Пользователь
 
Регистрация: 03.11.2013
Сообщений: 37
По умолчанию

Ну можно, наверно, я не сильно в этом шарю.
Тетрадь вне форума Ответить с цитированием
Старый 23.09.2014, 21:11   #12
min@y™
Цифровой кот
Старожил
 
Аватар для min@y™
 
Регистрация: 29.08.2014
Сообщений: 7,629
По умолчанию

Давай до завтра, щас сильно влом кодить с нуля. Я на диване лежу, неудобно.
Расскажу я вам, дружочки, как выращивать грибочки: нужно в поле утром рано сдвинуть два куска урана...
min@y™ вне форума Ответить с цитированием
Старый 24.09.2014, 11:10   #13
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,229
По умолчанию

такая программа устроит?
Код:
{Составить программу для проверки, можно ли N представить в виде произведения двух простых чисел}

function isPrime(X: LongInt): boolean;
var i: integer;
  xsqrt : longint;
Begin
     isPrime:=false;
     if x<2 then Exit;
     if not odd(x) and (x<>2) { проверяем на чётность  }
          then exit;
     i:=3;
     xsqrt := trunc( sqrt(x) );
     while i <= xsqrt do { проверяем только нечётные }
     begin
          if x mod i = 0 then Exit;
          inc(i,2);
     end;
     isPrime:=true;
End;

var i, N : LongInt;
    k : integer;
begin
   WriteLn('Введите число N:');
   ReadLn(N);
   k := 0;
   if isPrime(N)
     then WriteLn('Число ',N,' простое и не может быть представлено в виде произведения 2-х простых чисел.')
     else
       for i:=2 to trunc( sqrt(N) ) do
         if ((N mod i)=0) and isPrime(i) and isPrime(N div i) then begin
           WriteLn(N,'  = ',i,' * ',N div i);
           inc(k)
         end;
   WriteLn;
   if k=0 then WriteLn('Число ',N,' не может быть представлено в виде произведения 2-х простых чисел.');

   WriteLn('Нажмите ENTER для выхода');
   Readln;
end.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 24.09.2014, 14:33   #14
min@y™
Цифровой кот
Старожил
 
Аватар для min@y™
 
Регистрация: 29.08.2014
Сообщений: 7,629
Смех Ещё вариантик...

Решил сделать прогу, заточенную как под турбопаскакаль, так под delphi (консольную). Причём, с возможностью поиска простых чисел как "на лету", так и в константном массиве (исходник массива - в прицепе). Интересно было скорости сравнить.
Короче, вот:
Код:
{
Составить программу для проверки, можно ли
 заданное натуральное число N представить
в виде произведения двух простых чисел.

Из википедии
(http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D1%81%D1%82%D1%8B%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0):
Простое число — это натуральное (целое положительное) число, имеющее ровно
два РАЗЛИЧНЫХ натуральных делителя.
}

{
  0...65535 - все числа, умещающиеся в 16 бит без знака.
  Создаду массив, в котором каждый бит (0/1 false/true)
  показывает, является ли число №[нечётного_числа] простым.
  Всего чисел - 65536 штук. Из них нечётных - половина - 32768 штук.
  Если элементы массива брать 16-битными (Word), значит каждый
  элемент будет содержать инфу о 16 числах, а сам массив будет
  иметь размер 32768/16 = 2048 элементов по 2 байта на элемент,
  итого 4 кбайт.

  Если надо без использования массива - удалить вот эту скобку ---> }
{$define USE_CONSTANTS}

program p265836;

{$ifdef WIN32}
{$APPTYPE CONSOLE}

uses
  SysUtils;
{$else}
uses
  CRT;
{$endif}

{$ifdef USE_CONSTANTS}
{$include Primes16.inc}

{ Проверка числа Х на простоту через массив Primes16 (быстро). }
function IsPrime16(const X: Integer): Boolean;
var
  Index, Mask: Word;
  {$ifndef WIN32}
  Result: Boolean;
  {$endif}
begin
  { по умолчанию должно быть натуральным нечётным или = 2 }
  Result:= ((X > 0) and Odd(X)) or (X = 2);

  if Result and (X > 3)
    then begin
           Index:= X div 32;
           Mask:= 1 shl ((X div 2) mod 16);
           Result:= (Primes16[Index] and Mask) <> 0;
         end;

  {$ifndef WIN32}
  IsPrime16:= Result;
  {$endif}
end;

{$else}

{ Проверка числа Х на простоту без массива Primes16 (на лету, медленно). }
function IsPrime16(const Value: Integer): Boolean;
var
  Divider, Limit: Integer;
  {$ifndef WIN32}
  Result: Boolean;
  {$endif}
begin
  Result:= True;

  if (Value > 3) and Odd(Value)
    then begin
           Limit:= Trunc(Sqrt(Value));
           Divider:= 2;

           while Divider <= Limit do
             if Value mod Divider = 0
               then begin
                      Result:= False;
                      Break;
                    end
               else Inc(Divider);
         end;

  {$ifndef WIN32}
  IsPrime16bit:= Result;
  {$endif}
end;
{$endif USE_CONSTANTS}

{ Проверка возможности разложения числа N на 2 простых множителя.
  Если возможно, функция возвратит True, а сами множители -
  в параметрах A и B.
  Если число N простое, то A = N, B = 1.}
function Factorized(const N: Integer; out A, B: Integer): Boolean;
var
  x1, x2: Integer;
  Limit: Word;
  {$ifndef WIN32}
  Result: Boolean;
  {$endif}
begin
  Result:= False;

  { Если N - простое, значит оно не может быть произведением двух целых,
    кроме себя и 1. }
  if IsPrime16(N)
    then begin
           A:= N;
           B:= 1;
         end

  { иначе проверяю пары чисел от 2 до int(sqrt(N): )
    последовательно делю X на простое число в диапазоне от 2 до int(sqrt(N),
    если результат от деления - простое число, значит число N представить
    в виде произведения двух простых чисел МОЖНО }
    else begin
           Limit:= Trunc(Sqrt(N));

           for x1:= 2 to Limit do
             if (IsPrime16(x1)) and (N mod x1 = 0)
               then begin
                      x2:= N div x1;

                      if IsPrime16(x2)
                        then begin
                               Result:= True;
                               A:= x1;
                               B:= x2;
                               Break;
                             end;
                    end;
         end;

  {$ifndef WIN32}
  Factorized:= Result;
  {$endif}
end;

var
  X, N, A, B: Integer;
  Total: Integer;

begin
  {$ifndef WIN32}
  ClrScr;
  {$endif}

  repeat
    repeat
      Write('  Enter value [1 < N < 32768], or "0" for exit: ');
      ReadLn(N);
    until (N < $8000);

    { проверка одиночного числа N:
    if Factorized(N, A, B) 
      then WriteLn('   ', N, ' = ', B, ' x ', A)
      else WriteLn('   ', N, ' - no match found.');
    }

    { поиск и проверка чисел от 2 до N включительно: }
    Total:= 0;
    for X:= 2 to N do
      if Factorized(X, A, B)
        then begin
               Inc(Total);
               WriteLn('   ', X: 5, ' = ', B: 5, ' x ', A);
             end;
    if N > 1
      then WriteLn('   Total found: ', Total, ' of ', N - 1, ' (', (100 * Total / (N - 1)) : 3: 3, '%)'#13#10);
  until N = 0;
end.
Ахтунг! ТурбоПаскакалем не компилил, ибо влом ковырять DosBox было.
Изображения
Тип файла: jpg screen.jpg (22.6 Кб, 124 просмотров)
Вложения
Тип файла: zip Primes16.inc.zip (5.3 Кб, 3 просмотров)
Тип файла: zip Primes16.txt.zip (131.6 Кб, 4 просмотров)
Расскажу я вам, дружочки, как выращивать грибочки: нужно в поле утром рано сдвинуть два куска урана...

Последний раз редактировалось min@y™; 24.09.2014 в 14:41.
min@y™ вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Можно число N представить в виде произведения двух простых чисел? Тетрадь Помощь студентам 0 19.09.2014 17:18
создание програмы на делфи циклы:ввести натуральное число и определять, можно ли число представить в виде суммы двух простых чисел Костяхалк Помощь студентам 24 28.01.2014 08:48
Представить n в виде произведения простых чисел akademochka Общие вопросы C/C++ 24 23.03.2013 12:13
Можно ли число N представить в виде сумы двух квадратов натуральных чисел? Dima170792 Помощь студентам 2 24.06.2011 08:53
Дано натуральное число n. Можно ли представить его в виде суммы двух квадратов натуральных чисел? Сеня Помощь студентам 3 29.01.2009 01:17