KTLT 5. Tổng 4 số nguyên tố

Tiêu đề: KTLT 5. Tổng 4 số nguyên tố Tue May 10, 2022 4:28 pm

5) TỔNG 4 SỐ NGUYÊN TỐ
Cho số nguyên dương x (1 ≤ x ≤ 1500). Hãy xác định số cách phân tích x thành tổng 4 số nguyên tố: x = a + b + c + d, trong đó 1 ≤ a ≤ b ≤ c ≤ d.
Ví dụ, với x = 8 ta có 1 cách phân tích:
8 = 2 + 2 + 2 + 2;
Dữ liệu: Vào từ file văn bản SUMPRIME.INP gồm nhiều tests, mỗi test cho trên một dòng chứa một số nguyên x.
Kết quả: Đưa ra file văn bản SUMPRIME.OUT, kết quả mỗi test đưa ra trên một dòng dưới dạng số nguyên.
Ví dụ:
SUMPRIME.INP
8
SUMPRIME.OUT
1
SUMPRIME.INP
9
SUMPRIME.OUT
1

Tiêu đề: Re: KTLT 5. Tổng 4 số nguyên tố Thu May 12, 2022 3:23 pm

Thuật toán:
Vì x = a + b + c + d với a <= b <= c <= d

Code:: For(a)
for(b)
for(c)
{
ngto(a), ngto(b), ngto(c), ngto(x - a - b -c) và 1 điều kiện (x - a - b - c > 0)
}

Chuyển đổi thành:

Code:: for (a)
  ngto(a)
   for(b)
   ngto(b)
   for(c)
   ngto(c)
   (x - a - b - c > 0 && ngto(x-a-b-c))
   res++;

Đểm giảm việc kiểm tra tính nguyên tố nhiều lần ta sử dụng Sàng Eratosthenes tới X thu được mảng F.

Code:: for (a)
  F[a]
   for(b)
   F[b]
   for(c)
   F[c]
   (x - a - b - c > 0 && ngto(x-a-b-c))
   res++;

Độ phức tạp thuật toán: O(X^3 + X) ~ O (X^3).

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

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

int x,coun,x4;
bool NT[1501];

void nhap()
{
   cin >> x;
   x4 = x/4+1;
}

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

}

int main()
{
   ios_base::sync_with_stdio(false); cin.tie(0);
   freopen("xdd.inp","r",stdin);
freopen("xdd.out","w",stdout);
   nhap(); sang(x);
   for (int a=0; a<=x4; a++)
   if (NT[a] == true)
   for (int b=a; b<=x4; b++)
   if (NT[b] == true)
   for (int c=b; c<=x4; c++)
   if (NT[x-a-b-c] == true && x-a-b-c >= c)
   {
   coun++;
   }
   cout << coun;
   return 0;
}

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

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

int dem,x;

bool y[100001];

void sang()
{
memset(y,true,sizeof(y));
y[1] = false;
for(int i =1; i <= x; i++)
{
int j = 2;
if(y[i])
while(i*j <= x)
{
y[i*j] = false;
j++;
}
}

}

void nhap()
{
cin>>x;
}
void sol()
{
sang();
// for(int i =1; i <= x; i++) cout<<y[i]<<" "<<i<<endl;
for(int a = 2; a <= x/4 + 1; a++)
for(int b = 2; b < x/4 + 1; b++)
if(y[b])
for(int c = 2; c <= x/4 + 1; c++)
if(x - a - b - c >= c && y[x - a - b - c]) ++dem;
cout<<dem;
}
int main()
{
nhap();
sol();
}

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

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

int x,coun,spp;
bool ngto[1505];

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

}

int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
freopen("sumprime.inp","r",stdin);
freopen("sumprime.out","w",stdout);
cin >> x;
spp = x/4 +1;
sangnt(x);
for (int a=0; a<=spp; a++)
if (ngto[a] == 1)
for (int b=a; b<=spp; b++)
if (ngto[b] == 1)
for (int c=b; c<=spp; c++)
if (ngto[x-a-b-c] == 1 && x-a-b-c>=c)
{
coun++;
}
cout << coun;
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;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie();
freopen("sumprime.inp","r",stdin);
freopen("sumprime.out","w",stdout);
cin >> n;
bool f[10000];
f[1]=false;
for (int i=2;i<=n;i++) f[i]=true;
for (int i=2;i<=n;i++)
if (n%i==0)
for (int j=i*2;j<=n;j+=i) f[j]=false;
int res=0;
for (int a=2;a<=n;a++)
if (f[a]==true)
for (int b=a;b<=n;b++)
if (f[b]=true)
for (int c=b;c<=n;c++)
if (n-a-b-c>=c&&f[n-a-b-c]==true) res++;
cout << res;
return 0;
}

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

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

int x,coun,x4;
bool NT[1507];

void inp()
{
   cin >> x;
   x4 = x/4+1;
}

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

}

int main()
{
   ios_base::sync_with_stdio(false); cin.tie(0);
   freopen("sumprime.inp","r",stdin);
   freopen("sumprime.out","w",stdout);
   inp(); nto(x);
   for (int a=0; a<=x4; a++)
   if (NT[a] == true)
   for (int b=a; b<=x4; b++)
   if (NT[b] == true)
   for (int c=b; c<=x4; c++)
   if (NT[x-a-b-c] == true && x-a-b-c >= c)
   {
   coun++;
   }
   cout << coun;
   return 0;
}

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

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

int x,dem=0;
bool nt[1501];

void nhap()
{
cin >> x;

}

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

}
void xuly()
{
for (int a=0; a<=x/4+1; a++)
if (nt[a] == true)
for (int b=a; b<=x/4+1; b++)
if (nt[b] == true)
for (int c=b; c<=x/4+1; c++)
if (nt[x-a-b-c] == true && x-a-b-c >= c)
{
dem++;
}
}
void in()
{
cout << dem;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
freopen("sumprime.inp","r",stdin);
freopen("sumprime.out","w",stdout);
nhap();
sang(x);
xuly();
in();
return 0;
}

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

#include<bits/stdc++.h>
#define nmax 1507

using namespace std;

int n;
bool check[nmax];

void prime(){
memset(check, 1, sizeof(check));
for(int i = 1; i <= nmax; i++){
if(check[i]) for(int j = 2*i; j <= nmax; j += i)
check[j] = 0;
}
}

void get(int n){
int d = 0;
int t = n/4 + 1;
for(int a = 0; a <= t; a++) if(check[a])
for(int b = a; b <= t; b++) if(check[b])
for(int c = b; c <= t; c++)
if(check[n - a - b - c] && ((n - a - b - c) > 0)) d++;
cout << d << '\n';
}

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
freopen("sumprime.inp", "r", stdin);
freopen("sumprime.out", "w", stdout);
prime();
while(cin >> n) get(n);
return 0;
}

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

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

int x,coun,spp;
bool ngto[1505];

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

}

int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
freopen("sumprime.inp","r",stdin);
freopen("sumprime.out","w",stdout);
cin >> x;
spp = x/4 +1;
sangnt(x);
for (int a=0; a<=spp; a++)
if (ngto[a] == 1)
for (int b=a; b<=spp; b++)
if (ngto[b] == 1)
for (int c=b; c<=spp; c++)
if (ngto[x-a-b-c] == 1 && x-a-b-c>=c) coun++;
cout << coun;
return 0;
}

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

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

int i,n,a,b,c,d,x,res=0;
int f[nmax];

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

void xuly()
{

for(int a=0;a<=n;a++)
if (f[a]==0)
for(int b=a;b<=n;b++)
if (f[b]==0)
for(int c=b;c<=n;c++)
if ((x-a-b-c>=c)&&(f[x-a-b-c]==0))
res++;
cout << res;

}

int main ()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> x;
n=x/4 + 1;
sangnt(x);
xuly();
return 0;
}

» KTLT 6) Tìm ước nguyên tố
» KTLT 9) SỐ ĐẸP 2
» KTLT 8) SỐ ĐẸP
» KTLT 10) TÍCH CÁC CHỮ SỐ
» KTLT 7) SỐ NGHỊCH THẾ