[Lập trình newbie] Mỗi ngày một bài toán (số 8)

[09520281]

Hi all, theo như một lời đề nghị của bạn Cao Văn An (CNPM) thì nên có một số bài cơ bản về số học để các bạn khóa sau tập làm quen và dễ dàng tiếp cận. Bài toán hôm nay rất ngắn gọn :salute:
Bài tập về số nguyên tố: Cho số n <= 2 tỉ, phân tích ra thừa số nguyên tố.
Time limit: 1s.
Memory: 5MB
Input:
Nhập số N.
Output:
Kết quả phân tích ra số nguyên tố
Ví dụ:
Input: 6
Output: 3,2

Have Fun

[09520500]

Ví dụ sai kìa?? 1 ko phải nguyên tố :go:

[09520281]

Ví dụ sai kìa?? 1 ko phải nguyên tố :go:

Đã fix, nhầm chút hehe

[11520132]

ví dụ không rõ ràng lắm, ví dụ như 9 thì print 3,3 hay print 3 thôi, 12 thì print 2,2,3 hay print 2,3 thôi

[09520281]

ví dụ không rõ ràng lắm, ví dụ như 9 thì print 3,3 hay print 3 thôi, 12 thì print 2,2,3 hay print 2,3 thôi

Nó in ra 12 = 3*2*2 => 3,2,2

[11520132]

Viết hơi khó hiểu 1 tý

#include <stdio.h>
int snt_thu_i(int a[],int i)
{
    if (i==0) return 2;
    int j,k;
    for (j=a[i-1]+1;;j++)
    {
        for (k=0;k<i;k++)
            if (j%a[k]==0) break;
            else if (a[k]*a[k]>j)
            {
                a[i]=j;
                return j;
            }
    }
}
void xuat(int n,int a[])
{
    int i;
    for (i=0;snt_thu_i(a,i)<=n;i++)
    {
        if (n%a[i]==0)
        {
            printf("%3d",a[i]);
            n=n/a[i--];
        }
    }
}
int main()
{
    int a[150000];
    a[0]=2;
    int i,n;
    scanf("%d",&n);
    xuat(n,a);
} 

[08520001]

Code của bạn khó hiểu giay nam vnxk. mà bạn cũng chẳng viết thuật toán ra nữa.

Với lại khi chạy với n = 1999999989 thì nó bị lỗi

[11520132]

Code của bạn khó hiểu, mà bạn cũng chẳng viết thuật toán ra nữa. Với lại khi chạy với n = 1999999989 thì nó bị lỗi

thuật toán là tạo ra một mảng số nguyên tố, bắt đầu từ số 2, khi nào nó không chia hết cho snt đó thì mới tìm số nguyên tố tt.
Ví dụ n=6;
a[0]=2.
6 chia hết cho 2, in 2 ra màn hình, n=n/a[0]=3.
3 không chia hết cho 2, tìm snt tiếp theo -> a[1]=3;
3 chia hết cho 3, in 3 ra màn hình. n=n/a[1]=1;
lúc này snt_thu_i>n nên dừng lại.
Cái số 1999999989=3*3*13*17094017. Cái số 17094017 là snt thứ 1096992, mà cái mảng khai 150k cho nên chạy không được.
mà khai báo lớn quá cũng không được, có thể dùng cấp phát bộ nhớ mà thực hiện lâu quá. Kiếm thuật toán khác thôi.

[11520132]

mà số lớn quá à, chẳng hạn e cho số nguyên tố 2,038,074,743 là số nguyên tố thứ 100 triệu, kiểm tra nó có là số nguyên tố hay không cũng đã hơn 1s rồi. Ai có thuật toán kiểm tra <1s thì cho em mượn

[11520447]

Tìm các số nguyên tố từ 2 đến N/2 , gắn nó vào mảng A[];
Chia N cho A[i] :
+ nếu chia hết thì in A[i] và N/=2;
+ Chia ko hết thì i++;

thuật toán của e như thế, chạy số chừng 500.000 là quá time
mà số lớn nữa thì ct ko chạy lun
ai chỉ e vs


---------------

ơ giống bạn trên kia rầu

[10520355]

cho i chạy tới căn n là được.

#include <iostream>
using namespace std;
int n;
void xuly( int a)
{
    for(int i=2; i*i<=a; i++)
        while(a%i==0) cout<<i<<" ", a/=i;
        (a>1)?cout<<a<<endl:cout<<endl;
}
int main()
{
    cin>>n; 
    xuly(n);
    return 0;
}

[11520132]

cho i chạy tới căn n là được.

#include <iostream>
using namespace std;
int n;
void xuly( int a)
{
    for(int i=2; i*i<=a; i++)
        while(a%i==0) cout<<i<<" ", a/=i;
        (a>1)?cout<<a<<endl:cout<<endl;
}
int main()
{
    cin>>n; 
    xuly(n);
    return 0;
}

hjx, đơn giản vậy mà nghĩ không ra, cứ thích nghĩ cao siêu cho vô mảng số nguyên tố mới ác

[08520001]

Kinh nghiệm!!! giay cong so nam. :happy:

[09520109]

mình có ý này mọi người tham khảo ha:
- cho vòng for chạy lùi từ căn bậc hai của số đó tới khi gặp số nguyên tố đầu tiên là ước của số đó thì dừng và đưa vào kết quả (tạm gọi là số a và thương là số b)
- tiếp theo lặp lại bước trên với số vào là thương b và vòng lặp bắt đầu từ a
- lăp lại 2 bước trên tới khi thương bằng 1 (b=1) thì kết thúc

[10520355]

mình có ý này mọi người tham khảo ha:
- cho vòng for chạy lùi từ căn bậc hai của số đó tới khi gặp số nguyên tố đầu tiên là ước của số đó thì dừng và đưa vào kết quả (tạm gọi là số a và thương là số b)
- tiếp theo lặp lại bước trên với số vào là thương b và vòng lặp bắt đầu từ a
- lăp lại 2 bước trên tới khi thương bằng 0 (b=0) thì kết thúc

theo em thấy lỗi ý tưởng của anh thế này:
-về mặt lập trình thì mình phải viết thêm 1 hàm xét số đó có phải là số nguyên tố hay không, sử dụng thêm thư viện math.h và hàm sqrt để tính căn bậc 2 của một số nữa ==> làm chương trình mình dài ra.
-về thuật toán:
+chạy lùi dẫn đến kết quả là những con số giảm dần
+trong vòng for nếu mình sử dụng lệnh if để xét điều kiện số nguyên tố đầu tiên và là ước của số đó thì kết quả sẽ là tích các số nguyên tố không trùng nhau. sửa lại là dùng vòng while
ví dụ: nhập 2 tỉ vào thì kết quả là 5 và 2
+thương b sẽ không bao giờ bằng 0 vì đây là phép chia và số n ban đầu > 0 mà. b chỉ có thể >=1 thôi. Với số nhập vào là một số nguyên tố thì thương b sẽ luôn bằng chính số ban đầu, với số nhập vào có căn bậc hai nhỏ hơn số cuối cùng của kết quả thì nó sẽ xuất ra kết quả sai. ví dụ : n=6; 6=2x3;(int) sqrt(6)= 2; vậy vòng for chạy i từ 2 đến 2 ==> kết quả sẽ xuất ra 2 mà thôi, thiếu mất số 3 mất tiu. vì vậy sau khi xử lý bằng vòng for ở trên thì mình phải kiểm tra thương b sau cùng nếu > 1 (b có thể là số nguyên tố ban đầu nhập vào hoặc một số > căn bậc 2 ( số n ban đầu) ) thì mình xuất ra b.