Từ 1 tới 7 trên tổng số 7 kết quả

Đề tài: [help] phân tích 1 số rất lớn (khoảng 10^9) ra thừa số nguyên tố

  1. #1
    Ngày gia nhập
    10 2011
    Bài viết
    0

    Wink [help] phân tích 1 số rất lớn (khoảng 10^9) ra thừa số nguyên tố

    đề bài của em đây, các a chị cho em xin thuật toán tối ưu nhất, (phải chạy trong 1s)
    Cho số nguyên dương n (2<=n<=10^9) , hãy phân tích n ra thừa số nguyên tố.

    Dữ liệu:

    Một dòng duy nhất chứa số n.

    Kết quả:

    Mỗi dòng ghi một thừa số nguyên tố và số mũ tương ứng cách nhau bởi dấu cách.

    Các thừa số nguyên tố in ra theo thứ tự tăng dần.

    Ví dụ:

    INPUT


    OUTPUT

    4


    2 2

    INPUT


    OUTPUT

    168


    2 3

    3 1

    7 1

  2. #2
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    For đến căn (n) thôi
    C++ Code:
    1. #include<iostream>
    2. #include<vector>
    3. #include<math.h>
    4. using namespace std;
    5. void ff(long long n, vector<long long>&factor,vector<long long>&power)
    6. {
    7.     for (long long i=2;i*i<=n;i++)
    8.     {
    9.         if (n%i==0)
    10.         {
    11.             factor.push_back(i);
    12.             long long p;
    13.             for (p=0;n%i==0;p++)
    14.                 n=n/i;
    15.             power.push_back(p);
    16.         }
    17.     }
    18.     if (n>1)
    19.     {
    20.         factor.push_back(n);
    21.         power.push_back(1);
    22.     }
    23. }
    24. int main()
    25. {
    26.     long long n;
    27.     vector<long long>a,b;
    28.     cin>>n;
    29.     ff(n,a,b);
    30.     for (int i=0;i<a.size();i++)
    31.     cout<<a[i]<<" "<<b[i]<<endl;
    32.     system("pause");
    33.     return 0;
    34. }

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  3. #3
    Ngày gia nhập
    10 2011
    Bài viết
    0

    Code:
    999999999
    3 4
    37 1
    333667 1
    
    Process returned 0 (0x0)   execution time : 12.745 s
    Press any key to continue.
    vẫn 12s anh ơi.

  4. #4
    Ngày gia nhập
    07 2011
    Bài viết
    160

    10^9 là bình thường chứ chưa có gì là rất lớn cả. Bạn thử code này của mình coi (cách ghi output có hơi khác 1 tí tẹo, bạn tự chỉnh lại):

    http://diendan.congdongcviet.com/sho...495#post287495

    P.S: Thực ra chỉ khác cách của hunterphu vài cái nhỏ còn thuật toán là giống. Bạn chủ topic xem lại việc tính thời gian của bạn chứ mình chạy thử bài của hunterphu ra ngay lập tức (tính time thì bỏ pause đi).
    Đã được chỉnh sửa lần cuối bởi fbchicken : 05-11-2011 lúc 10:08 AM.

  5. #5
    Ngày gia nhập
    10 2011
    Bài viết
    3

    Trích dẫn Nguyên bản được gửi bởi hoangbao1510 Xem bài viết
    đề bài của em đây, các a chị cho em xin thuật toán tối ưu nhất, (phải chạy trong 1s)
    Cho số nguyên dương n (2<=n<=10^9) , hãy phân tích n ra thừa số nguyên tố.
    C++ Code:
    1. #include<iostream.h>
    2.  
    3. void factorization(unsigned long n, unsigned long a[], int b[], int &m)
    4. {
    5.     m = 0;
    6.     while (n > 1)
    7.     {
    8.         unsigned long k = 2;
    9.         while (n%k) k++;
    10.         if (m)
    11.         {
    12.             if (a[m-1] == k) b[m-1]++;
    13.             else
    14.             {
    15.                 a[m] = k; b[m] = 1; m++;
    16.             }
    17.         }
    18.         else
    19.         {
    20.             a[m] = k; b[m] = 1; m++;
    21.         }
    22.         n = n/k;
    23.     }
    24. }
    25.  
    26. void list(unsigned long a[], int b[], int m)
    27. {
    28.     for (int k = 0; k < m; k++)
    29.         cout << a[k] << " " << b[k] << endl;
    30. }
    31.  
    32. void main()
    33. {
    34.     unsigned long n = 999999999;
    35.     unsigned long a[10]; int b[10], m;
    36.    
    37.     factorization(n, a, b, m);
    38.     list(a,b,m);
    39. }

  6. #6
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    Mặc định [help] phân tích 1 số rất lớn (khoảng 10^9) ra thừa số nguyên tố

    Trích dẫn Nguyên bản được gửi bởi hoangbao1510 Xem bài viết
    Code:
    999999999
    3 4
    37 1
    333667 1
    
    Process returned 0 (0x0)   execution time : 12.745 s
    Press any key to continue.
    vẫn 12s anh ơi.
    Độ phức tạp của mình là O(căn(n)) mà , với n=10^9 thì căn(n)~ 32000 phép tính làm gì tới 12s

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  7. #7
    Ngày gia nhập
    10 2011
    Bài viết
    0

    Trích dẫn Nguyên bản được gửi bởi hunterphu Xem bài viết
    Độ phức tạp của mình là O(căn(n)) mà , với n=10^9 thì căn(n)~ 32000 phép tính làm gì tới 12s
    cám ơn a hunterphu, em đã làm được 0.98s ^^

Các đề tài tương tự

  1. Điện Tử Thái Thắng chuyên cung cấp ống nhòm đo khoảng cách, máy đo khoảng cách
    Gửi bởi thaithangtelecom trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 1
    Bài viết cuối: 28-07-2013, 09:04 PM
  2. Bài tập C Tìm 2 số nguyên tố trong khoảng 0 đến n có tổng = n.help me
    Gửi bởi Hoamy_it trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 3
    Bài viết cuối: 28-04-2012, 11:21 PM
  3. Hàm xóa khoảng ở đầu chuỗi không xóa hết khoảng trắng
    Gửi bởi taymonquang trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 5
    Bài viết cuối: 07-11-2011, 01:01 PM
  4. Bài tập C liệt kê số nguyên tố trong khoảng từ 2 đến 480000
    Gửi bởi coichettrove_teo trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 20
    Bài viết cuối: 16-01-2011, 03:20 AM
  5. Liệt kê các cặp nguyên tố cùng nhau trong khoảng [P,Q], với P,Q nhập từ bàn phím
    Gửi bởi linkinpark trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 6
    Bài viết cuối: 28-12-2010, 10:12 PM

Tags của đề tài này

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn