Экспертная система Delphi.int.ru

Сообщество программистов
Общение, помощь, обмен опытом

Логин:
Пароль:
Регистрация | Забыли пароль?

Delphi.int.ru Expert

Другие разделы портала

Переход к вопросу:

#   

Статистика за сегодня:  


Лучшие эксперты

DNK
I. DNK
Баллы: 5

Подробнее »



Вопрос # 1 974

/ вопрос открыт /

Здравствуйте! Дали вот мне задачу...вроде не сложная...а вот че то не получается...в общем нужно сделать так чтобы при нажатии на кнопку в memo появились все простые числа в диапазоне от 1 до 100...нужно сделать либо через for либо через while либо через repeat

Anrie Вопрос ожидает решения (принимаются ответы, доступен мини-форум)

Вопрос задал: Anrie (статус: Посетитель)
Вопрос отправлен: 7 октября 2008, 18:58
Состояние вопроса: открыт, ответов: 4.

Ответ #1. Отвечает эксперт: ANBsoft

Здравствуйте, Anrie!
Может не очень оптимально, но просто
Var f,n:Integer;
b:Boolean;
begin
for f:=1 to 100 do begin
b:=True;//Признак того что число простое
for n:=2 to f-1 do
if f mod n =0 then b:=False;
if b then Memo1.Lines.Add(IntToStr(f));
end;
end;

Ответ отправил: ANBsoft (статус: Студент)
Время отправки: 7 октября 2008, 19:25
Оценка за ответ: 5

Комментарий к оценке: спасибо

Ответ #2. Отвечает эксперт: seryoga

Здравствуйте, Anrie!
unit Unit1;

interface

uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;

type
mass = array [1..25] of integer;
TForm1 = class(TForm)
Memo1: TMemo;
Button1: TButton;
procedure Button1Click(Sender: TObject);

private
{ Private declarations }
public
{ Public declarations }
procedure search;
end;

var
Form1: TForm1;
a:mass;
sizeA:integer;
implementation

{$R *.dfm}

{ TForm1 }

procedure TForm1.search;
var i,j:integer; fl:Boolean;
begin
a[1]:=2;
a[2]:=3;
sizea:=2;
for i:=5 to 100 do begin
fl:=false;
for j:=1 to sizea do
if i mod a[j] = 0 then fl:=true;
if not(fl) then
begin
inc(sizea);
a[sizea]:=i;

end;
end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var i:integer;
begin
search;
for i:=1 to sizeA do
Memo1.Lines.Add(inttostr(a[i]));
end;

end.

Ответ отправил: seryoga (статус: 1-ый класс)
Время отправки: 7 октября 2008, 19:34

Ответ #3. Отвечает эксперт: Помфюк Владимир Степанович

Здравствуйте, Anrie!
Так же просто. но немного оптимальнее:

memo1.lines.clear;
memo1.lines.add('1');//деление на 1 проверять не будем
memo1.lines.add('2');//добавляем чтобы в первый раз сработал цикл от 1 до memo.lines.count-1 (2-1=1 for j:=1 to 1)
for i:=3 to 100 do begin
b:=True;
for j:=1 to memo1.lines.count-1 do
if (i mod StrToInt(memo1.lines[j]) = 0) Then b:=False;
if b then memo1.lines.add(IntToStr(i));
end;

можно ещё оптимальнее: 2 мы уже добавили, и соответственно уже знаем что все чётные числа нам не нужны:
memo1.lines.clear;
memo1.lines.add('1');
memo1.lines.add('2');
for i:=2 to 50 do begin //цикл в два раза быстрее
b:=True;
for j:=1 to memo1.lines.count-1 do
if ((i*2-1) mod StrToInt(memo1.lines[j]) = 0) Then b:=False;
if b then memo1.lines.add(IntToStr(i*2-1)); //2*2-1 = 3 , 50*2-1=99
end;

Ответ отправил: Помфюк Владимир Степанович (статус: Абитуриент)
Время отправки: 7 октября 2008, 19:46

Ответ #4. Отвечает эксперт: Паровоз

Здравствуйте, Anrie!
Вот еще решето Эратосфена:
http://alglib.sources.ru/numbers/erat.php

Ответ отправил: Паровоз (статус: 10-ый класс)
Время отправки: 7 октября 2008, 21:43


Мини-форум вопроса

Всего сообщений: 20; последнее сообщение — 10 октября 2008, 15:25; участников в обсуждении: 8.
Dron

Dron (статус: Студент), 7 октября 2008, 19:26 [#1]:

Цитата:

нужно сделать либо через for либо через while либо через repeat

Так и напрашивается вопрос: а есть другие варианты?
С уважением.
seryoga

seryoga (статус: 1-ый класс), 7 октября 2008, 19:34 [#2]:

unit Unit1;

interface

uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;

type
mass = array [1..25] of integer;
TForm1 = class(TForm)
Memo1: TMemo;
Button1: TButton;
procedure Button1Click(Sender: TObject);

private
{ Private declarations }
public
{ Public declarations }
procedure search;
end;

var
Form1: TForm1;
a:mass;
sizeA:integer;
implementation

{$R *.dfm}

{ TForm1 }

procedure TForm1.search;
var i,j:integer; fl:Boolean;
begin
a[1]:=2;
a[2]:=3;
sizea:=2;
for i:=5 to 100 do begin
fl:=false;
for j:=1 to sizea do
if i mod a[j] = 0 then fl:=true;
if not(fl) then
begin
inc(sizea);
a[sizea]:=i;

end;
end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var i:integer;
begin
search;
for i:=1 to sizeA do
Memo1.Lines.Add(inttostr(a[i]));
end;

end.
seryoga

seryoga (статус: 1-ый класс), 7 октября 2008, 19:56 [#3]:

to: Помфюк Владимир Степанович и ты считаешь что твой метод оптимальней?
ANBsoft

ANBsoft (статус: Студент), 7 октября 2008, 20:03 [#4]:

Если хотите ускорить выполнение, то:
1) не нужно перебирать четные числа больше 2
2) как только признак простого стал False - выход из перебора
3) не нужно перебирать делители больше (n div 2+1)
ANBsoft

ANBsoft (статус: Студент), 7 октября 2008, 20:04 [#5]:

то Dron: можно еще через goto :)
Мережников Андрей

Мережников Андрей (статус: Абитуриент), 7 октября 2008, 20:08 [#6]:

to Помфюк Владимир Степанович
Ваш последний вариант можно сделать еще оптимальнее, заменив цикл for J:=1... на следующую конструкцию:
b:=false;
j:=1;
repeat
b:=((i*2-1) mod StrToInt(memo1.lines[j]) = 0);
inc(j);
until (b)or(j=memo1.lines.count);
Зачем проверять делением на весь список, если уже встретится число, на которое делится без остатка.

to Бубырь Александр Николаевич
то, что Ваше решение "не очень оптимально" - это мягко сказано. можно элементарно оптимизировать заменив for n:=2 to f-1
на for n:=2 to (f div 2) Хотя про цикл for в данном случае я написал выше
Dron

Dron (статус: Студент), 7 октября 2008, 20:11 [#7]:

Цитата:

можно еще через goto :)

Да, о таком извращении я не подумал...
С уважением.
ANBsoft

ANBsoft (статус: Студент), 7 октября 2008, 20:12 [#8]:

Скорее всего это задача по информатике в каком-то институте, моего решения вполне достаточно (чем проще тем лучше - меньше объяснять преподавателю что для чего), если нет - я привел варианты ускорения.
Мережников Андрей

Мережников Андрей (статус: Абитуриент), 7 октября 2008, 20:24 [#9]:

to Seryoga
Вариант, предложенный Помфюком действительно оптимальней в плане выполнения - проверка выполняется только делением на уже найденные простые числа - это самый оптимальный вариант. (с учетом прекращения проверки при обнаружении делителя)
seryoga

seryoga (статус: 1-ый класс), 7 октября 2008, 20:29 [#10]:

to Мережников Андрей а у меня как не так что ли?
Мережников Андрей

Мережников Андрей (статус: Абитуриент), 7 октября 2008, 20:29 [#11]:

Конечно, если не считать варианта заполнения memo вручную из таблицы простых чисел:
with memo1.lines do
add('1');
add('2');
add('3');
add('5');
.....
add('...');
end;
to Dron - вот вам еще вариант кроме циклов и go to :-)
Мережников Андрей

Мережников Андрей (статус: Абитуриент), 7 октября 2008, 20:34 [#12]:

to Seryoga - извини, я не уточнил, что сравнивал с вариантом, предложенным Бубырь Александром
А в предложенном Вами варианте есть небольшой недостаток - для того, чтобы задать размер массива, либо надо знать точное количество простых чисел, либо использовать динамический массив. Согласитесь, что при изменении диапазона, например до 1000 знать количество простых чисел проблематично.
Вадим К

Вадим К (статус: Академик), 7 октября 2008, 23:57 [#13]:

Можно ещё оптимальней написать перебор. Проверять не до (m div 2), а до целой части корня квадратного с проверяемого числа. Конечно, сюда стоит включить только нечетные числа.
Конечно, если считать простые числа до сотни. то это не сильно будет заметно. А вот до миллиона - это уже заметно, так как в моём случае время будет расти обратно пропорционально квадрату, а в случае m/2 - линейно.
Галочка "подтверждения прочтения" - вселенское зло.
Помфюк Владимир Степанович

Помфюк Владимир Степанович (статус: Абитуриент), 8 октября 2008, 10:25 [#14]:

to Seryoga:
когда я начинал писать свой ответ, то был только Ответ №1. Мой вариант был немного быстрее
seryoga

seryoga (статус: 1-ый класс), 8 октября 2008, 11:06 [#15]:

to Мережников Андрей:
Количество простых чисел r не превышает:

* trunc(1.6n/ln(n)+1), если n ≤ 200
* trunc(n/(ln(n)-2)+1), если n > 200
ANBsoft

ANBsoft (статус: Студент), 8 октября 2008, 11:24 [#16]:

Да хватит меряться у кого длиннее быстрее. Судя по формулировке задачи (как я уже писал), это нужно для получения зачета по информатике, и изголяться, экономя каждый такт процессора, нет смысла (судя по тому, что автор не появляется - он получил что хотел). Практический смысл от такого алгоритма очень мал, требуемые в криптографии простые числа получают совсем другими путями.
Anrie

Anrie (статус: Посетитель), 10 октября 2008, 14:55 [#17]:

Спасибо большое что помогли...я просто еще всего лишь в 11 классе и еще только начинаю изучать делфи...вот мне задали на уроке задачу повышенного уровня...ну это по сравнению с остальными одноклассниками....у меня были варианты...но я не смог додуматься до переменной типа boolean...
Вадим К

Вадим К (статус: Академик), 10 октября 2008, 15:06 [#18]:

по поводу boolean. А многие здесь на сайте вкурсе, что выражение вида
var c:boolean;
begin
c := 3 = 3;
вполне законно?
Галочка "подтверждения прочтения" - вселенское зло.
Помфюк Владимир Степанович

Помфюк Владимир Степанович (статус: Абитуриент), 10 октября 2008, 15:13 [#19]:

некоторые знают. но некторые предпочитают писать
c:=(3=3);
чтобы понятнее было :-)
Пупкин В.В.

Пупкин В.В. (статус: 1-ый класс), 10 октября 2008, 15:25 [#20]:

я догадовался об этом! :=)

Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.

Версия движка: 2.6+ (26.01.2011)
Текущее время: 17 августа 2017, 18:18
Выполнено за 0.06 сек.
Рейтинг@Mail.ru