KTLT 6) Tìm ước nguyên tố

Tiêu đề: KTLT 6) Tìm ước nguyên tố Tue May 10, 2022 4:40 pm

6) TÌM ƯỚC GCD.*
Nhập số nguyên dương N. Liệt kê các ước nguyên tố của N.
Ví dụ: N = 10; Các ước nguyên tố 2, 5.
GCD.INP
10
GCD.OUT
2 5

Tổng số bài gửi : 71 Join date : 10/05/2022

Code:: #include <bits/stdc++.h>
using namespace std;

int n;
bool NT[100001];

void nhap()
{
cin >> n;
}

void sang(int temp)
{
memset(NT,true,sizeof(NT));
NT[0] = false;
NT[1] = false;
for (int i=2; i<=n; i++)
if (NT[i] == true)
for (int j=2*i; j<=n; j+=i)
NT[j] = false;
}

int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
nhap(); sang(n);
if (NT[n] == true) {cout << n; return 0;}
for (int i=2; i<=n/2; i++)
if (n%i == 0 && NT[i] == true)
cout << i << " " ;
return 0;
}

Được sửa bởi Admin ngày Thu May 12, 2022 4:19 pm; sửa lần 2.

Thuật toán:
Subtask1

Code:: - for (i,1, i*i<=N)
nếu i là ước của N thì
{
ngto(i) thì đẩy i
{
k++;
c[k] = i;
}
nếu i != N/i và ngto(N/i) thì
{
k++;
c[k] = N/i;
}

- Sắp xếp mảng C có K phần tử.
- Đưa mảng C ra.

Subtask2:

Code:: - Phân tích N thành tích các thừa số nguyên tố lưu vào mảng C.
Ví dụ: N = 100, C = {2, 2, 5, 5}
- Đếm số phần tử khác nhau của mảng C.
Độ phức tạp thuật toán: O(Căn(N)).

Có thể dùng kiểu tập hợp Set để lưu nghiệm khác nhau thay vì sử dụng mảng C.

Tổng số bài gửi : 13 Join date : 10/05/2022

Code:: #include <iostream>

using namespace std;
int n,f[1000007];
int main()
{
int i=2;
cin >> n;
while(n>1)
{
if(n%i==0)
{
if(f[i]==0)
{
cout << i << " ";
f[i]=1;
}
n/=i;
}
else i++;
}
//cout << "Hello world!" << endl;
return 0;
}

Tổng số bài gửi : 71 Join date : 10/05/2022

Code:: #include <bits/stdc++.h>
using namespace std;

int n;
bool NT[100001];
vector <int> ans;

void nhap()
{
cin >> n;
}

void sang(int temp)
{
memset(NT,true,sizeof(NT));
NT[0] = false;
NT[1] = false;
for (int i=2; i<=n; i++)
if (NT[i] == true)
for (int j=2*i; j<=n; j+=i)
NT[j] = false;
}

int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
nhap(); sang(n);
if (NT[n] == true) {cout << n; return 0;}
for(int i=2;i<=n;i++)
if (n%i == 0 && NT[i] == true)
{
while (n%i == 0)
n /= i;
ans.push_back(i);
}
for (int x : ans) cout << x << " ";
return 0;
}

Tổng số bài gửi : 19 Join date : 09/05/2022

Code:: #include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n,c[100];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie();
freopen("gcd.inp","r",stdin);
freopen("gcd.out","w",stdout);
cin >> n;
int k=0;
for (int i=2;i<=sqrt(n);i++)
{
while (n%i==0)
{
k++;
c[k]=i;
n=n/i;
}
}
k++;
c[k]=n;
for (int i=1;i<=k;i++)
{
if (c[i]>c[i-1]) cout << c[i] << " ";
}
return 0;
}

Tổng số bài gửi : 14 Join date : 10/05/2022

Code:: #include <bits/stdc++.h>
using namespace std;
vector <int> vt;
int n,dem;
bool ngto[10005];
void sangnt(int u)
{
memset(ngto,1,sizeof(ngto));
ngto[0] = 0;
ngto[1] = 0;
for (int i=2; i<=u; i++)
if (ngto[i] == 1)
for (int j=2*i; j<=u; j+=i)
ngto[j] = 0;

}

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
sangnt(n);
for(int i=2; i<=n;i++)
{
if( n%i==0 && ngto[i] == 1)
{
vt.push_back(i);
}
}
sort( vt.begin(), vt.end() );
for(int i=0;i < vt.size();i++)
{
if(vt[i] != vt[i+1]) cout << vt[i] << " ";
}
return 0;
}

Tổng số bài gửi : 34 Join date : 13/06/2022

Code:: #include <bits/stdc++.h>
#define nmax 100007

using namespace std;

int n,i;
bool f[nmax];
vector <int> vt;

void sangnt(int u)
{
int i,j;
memset(f,1,sizeof(f));
f[0]=0;
f[1]=0;
for(int i=2;i<=u;i++)
if (f[i]==1)
for(int j=2*i;j<=u;j+=i)
f[j]=0;
}

int main()
{
cin >> n;
sangnt(n);
for(int i=2; i<=n;i++)
{
if( n%i==0 && f[i] == 1)
{
vt.push_back(i);
}
}
sort( vt.begin(), vt.end() );
for(int i=0;i < vt.size();i++)
{
if(vt[i] != vt[i+1]) cout << vt[i] << " ";
}
return 0;
}