Biểu diễn n giai thừa – Code trong C++ và Pascal

Like Tweet Pin it Share Share Email

Giai thừa N, ký hiệu N! là tích tất cả các số nguyên từ 1 đến N. Giai thừa N tăng rất nhanh, ví dụ 5!=120, 10!=3628800. Một cách để xác định số lớn như vậy, người ta chỉ ra số lần xuất hiện cacs số nguyên tố trong phân tích của nó ra thừa số nguyên tố. Ví dụ, sô 825 có thể xác định bởi dãy (0 1 2 0 1) có nghĩa là .

Cho một số nguyên dương N£1000. Hãy tìm cách biểu diễn số N! dưới dạng số lần xuất hiện các số nguyên tố trong phân tích n! ra các thừa số nguyên tố.

Dữ liệu vào từ file ANALYSE.INP gồm nhiều dòng, mỗi dòng chứa 1 số nguyên N (2£N£1000).

Kết quả Ghi ra file ANALYSE.OUT mỗi dòng tương ứng với 1 dòng trong file dữ liệu vào là dãy số thể hiện biểu diễn dưới dạng phân tích thành số nguyên tố của n! (phần tử cuối cùng của dãy phải là số dương).

Ví dụ:

ANALYSE.INP ANALYSE.OUT
10 8 4 2 1

Code trong C++

#include <bits/stdc++.h>
using namespace std;
bool nt[1005];
int a[1005];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    freopen("analyse.inp","r",stdin);
    freopen("analyse.out","w",stdout);
    for (int i=1; i<=1005; i++) nt[i]=1;
    nt[1]=0;
    for (int i=2; i<=sqrt(1005); i++)
        if (nt[i]==1)
        {
            int j=i*i;
            while (j<=1005)
            {
                nt[j]=0;
                j+=i;
            }
        }
    while (cin>>n)
    {

        memset(a,0,sizeof(a));
        for (int i=2; i<=n; i++)
        {
            int p=n,q=0;
            if (nt[i]==1)
            {
                while (p>=i)
                {
                    q=q+(p/i);
                    p=p/i;
                }
                a[i]=q;
            }
        }
        for (int i=2; i<=n; i++)
            if(nt[i]==1) cout<<a[i]<<" ";
        cout<<endl;
    }
return 0;
}

Code trong Pascal

var n,i,j,so,max:longint;
    D,P:array[2..1000000] of longint;
    f1,f2:text;

procedure sangnguyento(x:longint);
BEGIN
i:=2;
while i<=x do
  begin
  j:=i;
  while j<=x do
     begin
     j:=j+i;
     P[j]:=1;
     end;
  inc(i);
  end;
END;

procedure motep;
begin
assign(f1,'ANALYSE.INP');
reset(f1);
assign(f2,'ANALYSE.OUT');
rewrite(f2);
end;
procedure dongtep;
begin
close(f1);
close(f2);
end;
begin
motep;
while not eof(f1) do
  BEGIN
   readln(f1,n);
   max:=2;
   for i:=2 to n do
    begin
    so:=i;
    j:=2;
    while so<>1 do
      begin
        while so mod j=0 do
        begin
        inc(D[j]);
        so:=so div j;
        end;
      if j>max then max:=j;
      inc(j);
      end;
    end;
  sangnguyento(max);
  for i:=2 to max do if P[i]=0 then write(f2, D[i],' ');
  fillchar(D,sizeof(D),0);
  writeln(f2);
  END;
dongtep;
end.

Comments (0)

Trả lời

Your email address will not be published. Required fields are marked *