Tối ưu hơn bài toán tìm số có đúng 3 ước số

#1

image
image.png733×416 32.5 KB 

#include<iostream>
#include<cmath>

using namespace std;

bool isPrime(long long n){
	if(n<2)	return 0;
	else{
		for(long long i=2;i<=sqrt(n);i++){
			if(n%i==0) return 0;
		}
		return 1;
	}
}
int main(){
	int t; cin>>t;

	while(t--){
		long long n;cin>>n;
		int count=0;
		for(long long i=2;i<=sqrt(n);){
			if(isPrime(i))	count++;
			
			if(i%2==1)	i+=2;
			else if(i%2==0)	i++;
		}
		cout<<count<<endl;
	}
}

Trên là đề bài với code e làm nhưng máy nó chấm thì bị quá thời gian @@

#2

3 là số nguyên tố, 3-1=2, vậy chỉ có bình phương của số nguyên tố là thỏa đề :slight_smile: chạy sàng là xong cấp kỳ nhé :smiley:

4 Likes
#3

Chính xác, chỉ có bình phương cả số nguyên tố thỏa mãn!
Nhưng không hiểu đoạn này ý bạn là gì?

1 Like
#4

Khi phân tích thừa số nguyên tố của n có các số mũ lần lượt là a, b, c,… thì số ước của n là (a+1)(b+1)(c+1)… :slight_smile:

Công thức này với công thức tổng ước có cùng bản chất :smiley:

6 Likes
#5

e chay từ 1-> sqrt(n) xem số nào là số nguyên tố thì đếm thêm 1 lần nhưng bị timelimit

không biết a có cách nào sàng nó nhanh hơn k ???

#6

Sàng Eratosthenes đó mà :slight_smile:

3 Likes
#7 
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
//so co 3 uoc so => bình phuong cua SNT
long long prime16(long long n){
	long long result=0;
	vector<bool> isPrime;
	//khoi tao mang
	isPrime.push_back(0);//0
	isPrime.push_back(0);//1
	for(long long i=2;i<=n;i++){
		isPrime.push_back(1);
	}
	//xet
	for(long long i=2;i<=sqrt(n);i++){
		if(isPrime[i]==1){
			result++;
			for(int j=i*i;j<=n;j+=i){
				isPrime[j]=0;
			}
		}
	}
	//
	return result;
}

int main(){
	int t ; cin>>t;
	while(t--){
		long long n; cin>>n;
		cout<<prime16(n)<<endl;
	}
}

e chuyển sang sàng r vẫn bị timelimit chạy thử thấy nó lâu hơn cách trên

#8

sàng tới căn n thôi em :V

4 Likes
#9

e đọc thấy sàng dùng tốt cho đến 10^7 nhưng bài này giới hạn là 10^12

#10 
#include<iostream>
#include<cmath>

using namespace std;

bool isPrime(long long n) 
{ 

    if (n < 2) 
        return 0; 
    if (n <= 3) 
        return 1; 
 
    if (n % 2 == 0 || n % 3 == 0) 
        return 0; 
  
    for (long long i = 5; i * i <= n; i = i + 6) 
        if (n % i == 0 || n % (i + 2) == 0) 
            return 0; 
  
    return 1; 
} 
int main(){
	int t; cin>>t;

	while(t--){
		long long n;cin>>n;
		int count=0;
		for(int i=2;i<=sqrt(n);i++){
			if(isPrime(i))	count++;
		}
		cout<<count<<endl;
	}
}

cách tạm thời chấp nhận được (summit báo xanh) chưa phải tối ưu nhất
nguồn: geeksforgeeks

#11

Không cần sàng tới 10^12 đâu :smiley: mà phần sàng chỉ cần làm một lần, mỗi truy vấn đạt O(logN).

4 Likes
#12

Căn bậc 2 của 10^12 là 10^6, sàng nguyên tố đến 10^6 là đủ rồi. Các cơ số của bình phương cũng chỉ < 10^6 thôi.

5 Likes
#15

bạn DDD làm đc chưa
B1: bạn sàng snt (trên mạng có code nhé bạn !!)
B2: bạn duyệt các số nguyên tố vừa sàng , nếu bình phương số nào lớn hơn n thì k cout còn bé hơn or bằng thì cout

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?