Очередная несложная разминка

← →
MBo (2002-04-15 18:03) [0]

Тренировка для начинающих.

Составить программу разложения целых чисел, скажем, до 10000 на множители
пример вывода

2=prime
3=prime
4=2*2
...
10000=2*2*2*2*5*5*5*5 или 10000=2^4*5^4 по вкусу

← →
Андрей Сенченко (2002-04-15 18:49) [1]

Например в таком направлении ?
X := исходное число For i := 1 to 9 do begin IF X div Y = X / Y // -> сохраняем Y в массив решений, переназначаем результат в X Else BREAK IF X = 1 BREAK end;

← →
Андрей Сенченко (2002-04-15 18:51) [2]

По хорошему, цикл не
to 9, а to X/2 наверное

← →
Blackweber (2002-04-15 19:14) [3]

unit Unit1;

interface

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

type
TForm1 = class(TForm)
Edit1: TLabeledEdit;
Edit2: TLabeledEdit;
Button1: TButton;
Label1: TLabel;
Label2: TLabel;
procedure Button1Click(Sender: TObject);
end;

var
Form1: TForm1; e:integer;st:string;
a:array[1..100] of real;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
begin
st:=""; e:=0; edit2.Text:="";
a[1]:=strtofloat(edit1.Text);
repeat
inc(e);
a[e+1]:=trunc(log2(a[e]));
a[e+2]:=a[e]-power(2,a[e+1]);
st:=st+"2^"+floattostr(a[e+1])+" + ";
a[e+1]:=a[e+2];
until a[e+2]=0;
delete(st,length(st)-2,3);
edit2.Text:=st;
end;
end.

← →
Mystic (2002-04-15 23:34) [4]

Уже загадывал, но хорошей тренировкой будет программа на Delphi (консольная), которая выведет на экран собственный исходник (доступ к pas файлу запрещен, в ресурсы ничего не пихать и т. д.)

← →
Doom (2002-04-15 23:38) [5]

Задачки такие а ыв школе на бейсике делал помню.
> Андрей Сенченко © (15.04.02 18:51)
> По хорошему, цикл не
> to 9, а to X/2 наверное

Цикл до SQRT(X)

← →
MBo (2002-04-16 06:52) [6]

>Blackweber
это совсем не то - твоя процедура составляет число из степеней двойки. Замечу, что эта задача для двоек решается махом, стоит только вспомнить представление чисел в компе. Для другого основания твой способ с исправлениями в общем-то подходит.

← →
Alx2 (2002-04-16 08:00) [7]

Довольно объемный код, но заточенный под скорость.
Const PrimetblSize = 100; // Из-за разумных ограничений объема цитируемости таблицы, делаем ее размер = 100. Но здесь реально лучше использовать 10000. Иначе выигрыш по скорости незначителен. Const PrimeTable: Array[1..PrimetblSize] Of Integer = ( 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541); Function isPrime(A: Integer): Boolean; Forward; Procedure Divide(A, B: Integer; Var C, D: Integer); Assembler; Stdcall; // C=A div B; D = A mod B. Т.е. используем приятную особенность операции деления, позволяющую одновременно найти частное и остаток. asm mov eax,a cdq idiv b mov ecx,c mov [ecx],eax mov ecx,d mov [ecx],edx end; Function SearchNearestPrime(Pattern: Integer): Integer; Function Search(Start, Stop: Integer): Integer; Var C: Integer; Begin If Start < Stop Then Begin C := (Start + Stop) Shr 1; If PrimeTable[C] < Pattern Then Result := Search(C + 1, Stop) Else If PrimeTable[C] > Pattern Then Result := Search(Start, C - 1) Else Result := C; End Else If Start > Stop Then Result := Stop Else Result := Start End; Begin Result := Search(1, PrimetblSize); End; Function PrevPrime(A: Integer): Integer; Begin If (A > 2) And (A <= PrimeTable[PrimetblSize]) Then Begin Result := SearchNearestPrime(A); If PrimeTable[Result] >= A Then Result := PrimeTable[Result - 1] Else Result := PrimeTable[Result]; End Else If A <= 2 Then Result := 2 Else Begin dec(A); If A And 1 = 0 Then dec(A); While Not isPrime(A) Do dec(A, 2); Result := A; End; End; Function isPrime(A: Integer): Boolean; Var K: Integer; Begin If A < 0 Then A := -A; Result := (A <= 2) Or (PrimeTable[SearchNearestPrime(A)] = A); If Not Result Then Begin Result := ((A And 1) = 1); If Result Then Begin K := PrevPrime(Round(Sqrt(A)) + 1); While (K > 2) And (A Mod K <> 0) Do K := PrevPrime(K); Result := K = 2; End; End; End; весь сыр-бор здесь: После отработки iFactor List содержит разложение на простые множители числа A. Procedure iFactor(A: Integer; Lst: TList);</n> Var K : Integer; M, R: Integer; Begin If A < 0 Then A := -A; Lst.Clear; If (A <= 2) Or (isPrime(A)) // Если A - простое, то нечего и раскладывать Then Lst.Add(Pointer(A)) Else Begin K := PrevPrime(Round(Sqrt(A)) + 1); // Находим ближайшее с низу к квадратному корню из A простое число. While (K > 2) Do Begin Divide(A, K, M, R); // M = A div K; R = A mod K If (R = 0) Then // Если поделилось нацело, Begin // то продолжаем деление далее Repeat Lst.Add(Pointer(K)); A := M; Divide(A, K, M, R); Until (R <> 0); K := Round(Sqrt(A)) + 1 End; K := PrevPrime(K); End; If A And 1 = 0 Then // если A четное Begin // то дополняем List двойками Repeat Lst.Add(Pointer(2)); A := A shr 1; // Делим A на два // asm // shr A,1 // end; Until (A And 1) = 1; // Выходим, если A нечетное End; If (A > 1) Then Lst.Add(Pointer(A)); End; End;

← →
Alx2 (2002-04-16 08:13) [8]

Да, чуть не забыл описать идею:
Раскладывая число A, замечаем, что если A непростое, то наибольший член в разложении не превысит Round(Sqrt(A)) + 1.
Находим этот член, делим на него A и все повторяем снова. В итоге количество итераций O(log2(A))

← →
MBo (2002-04-16 08:31) [9]

OK, работает очень быстро.

← →
Nemesis (2002-04-16 09:50) [10]

Alx2 © (16.04.02 08:00)

Const
PrimeTable: Array[1..PrimetblSize] Of Integer = (
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541);

А автоматически расчитать все простые числа в некотором диапазоне слабо ...

← →
MBo (2002-04-16 10:07) [11]

не слабо ;)
вот глупый код
var
X: array [1..10000] of Boolean;
procedure ResetNoPrimes;
var
I, J: Integer;
begin
FillChar(X, SizeOf(X), True);
for I := 2 to 100 do
for J := I to 5000 do
if I * J <= 10000 then
X[I * J] := False;
end;

← →
Nemesis (2002-04-16 10:17) [12]

MBo © (16.04.02 10:07)

не слабо ;)

А почему там не вставил

← →
igorr (2002-04-16 11:14) [13]

To MBo, Alx2: А что значит быстро?

Предлагаю так.

type TForm1 = class(TForm) Edit1: TEdit; Button1: TButton; Label1: TLabel; procedure Button1Click(Sender: TObject); end; var Form1: TForm1; implementation {$R *.DFM} procedure TForm1.Button1Click(Sender: TObject); var Num, Simple:Integer; Str:String; begin Num:=StrToInt(Edit1.Text); Str:=Edit1.Text+"="; Simple:=2; while Num<>1 do begin if Num Mod Simple = 0 then begin Num:=Num Div Simple; Str:=Str+IntToStr(Simple)+" * "; Continue; end else Inc(Simple); end; Delete(Str,Length(Str)-2,3); Label1.Caption:=Str; end; end.

← →
Alx2 (2002-04-16 11:55) [14]

>Nemesis © (16.04.02 09:50)
>А автоматически расчитать все простые числа
>в некотором диапазоне слабо ...
Ты думаешь я их не автоматически искал? :))

← →
igorr (2002-04-16 12:06) [15]

Виноват. Континью - лишняя.

← →
MBo (2002-04-16 13:18) [16]

>igorr
ОК, работает

>А что значит быстро
числа от 2 до 10000 махом раскладывает
мой вариант намного медленнее, правда, он полностью функционально закончен, в него вывод встроен внутрь, что и тормозит, кроме того, простые насчитываются по ходу дела и хранятся (я его пока не приводил)

← →
MBo (2002-04-22 09:18) [17]

приведу свой вариант

procedure TForm1.Button2Click(Sender: TObject);
var
PrList:Tlist;
MulList:TStringList;
i,Num,Temp,MaxPrime:integer;
s:string;
N:integer;
begin
N:=10000;
PrList:=Tlist.Create;
PrList.Capacity:=100;
MulList:=TStringList.Create;
MulList.Capacity:=N;
for Num:=2 to N do begin
Temp:=Num;
MaxPrime:=2;
s:=IntToStr(Temp)+"=";
i:=-1;
while (Temp >= MaxPrime) and (i<PrList.Count-1) do begin
inc(i);
while (Temp >= MaxPrime) and (Temp mod Integer(PrList[i])=0) do begin
MaxPrime:=Integer(PrList[i]);
Temp:=Temp Div MaxPrime;
s:=s+IntToStr(MaxPrime)+"*";
end;
end;
if Temp=Num then begin
PRList.Add(Pointer(Num));
s:=s+"Prime";
end
else Delete(s,Length(s),1);
MulList.add(s);
end;
PrList.Free;
MulList.SaveToFile("C:\Primes.txt");
MulList.Free;
end;

Очередная несложная разминка Найти похожие ветки