Bình luận

• 
  

  0

  Sang_Nguyen_Dang    4:19 p.m. 19 Tháng 8, 2023

  python hơi căng xíu

• 
  

  10

  jumptozero    7:24 p.m. 4 Tháng 6, 2020

  Mình xin đóng góp lời giải bài này như sau:

  • Đầu tiên ta chú ý rằng: \(x\sim1e18\) ở đây là nhiễu, vì đề bài chỉ cần yêu cầu ta đếm số các số trong đoạn \([2;1e5]\) nhận \(x\) là ước nguyên tố nhỏ nhất. Do đó ta có thể suy ra ngay được rằng, nếu \(x>1e5\) thì đáp án là \(0\).
  • Do đó ta chỉ cần đi tính với các trường hợp \(x<=1e5\).
  • Cụ thể như sau:
  • Ta vẫn áp dụng thuật toán sàng nguyên tố thông thường, nhưng ở đây ta biến đổi tí xíu để phù hợp với bài toán:

  ll v[maxn];
  void f(ll n){
    bool prime[maxn];
    memset(prime,true,sizeof(prime));
    for(ll p=2;p*p<=n;p++){
      if(prime[p]==true){
          for(ll i=p*p;i<=n;i+=p) {if(prime[i]==true){prime[i]=false;v[p]++;} else continue;}
      }
    }
  }
  

  • Điểm khác biệt ở đây đó là mình đã sử dụng thêm mảng \(v\), trong đó \(v[i]\) chính là số các số trong đoạn \([2;1e5]\) nhận \(i\) làm ước nguyên tố nhỏ nhất.
  • Và cách đếm \(v[i]\) như sau:
  • Khi ta xác định được \(p\) là số nguyên tố (hay \(prime[p]==true\)) thì ngay sau đó nhiệm vụ ta cần làm đó là đi đếm số các số là bội của \(p\) (chính bằng \(v[p]\)) đồng thời gán các bội số \(prime[i]\) này thành \(false\). Nhưng để đếm không bị lặp thì ở mỗi lần gán các bội số \(prime[i]\) thành \(false\), ta cần phải kiểm tra xem ban đầu đã là \(true\) chưa. Nếu là \(true\) thì ta mới thực hiện, ngược lại thì không cần nữa, vì nếu làm nữa sẽ dẫn đến lặp số. (Đoạn này có vẻ khó hiểu, nhưng các bạn cứ yên tâm, mình có ví dụ phía dưới).
  • Mình lấy ví dụ như sau:
  • Bài toán 1: Giả sử ta đi đếm số lượng các số trong đoạn \([2;12]\) nhận \(2\) làm ước nguyên tố nhỏ nhất.
  • Bài toán 2: Giả sử ta đi đếm số lượng các số trong đoạn \([2;12]\) nhận \(3\) làm ước nguyên tố nhỏ nhất.
  • Rõ ràng ở bài toán \(1\), ta sẽ đi gán \(prime[4]=prime[6]=prime[8]=prime[10]=prime[12]=false\) và \(v[2]=5+1=6\) (Giải thích thêm: \(5\) ở đây là số bội của \(2\) (không tính \(2\)), còn \(1\) ở đây là cộng thêm chính số \(2\) đó )
  • Tiếp đến bài toán 2, nếu không kiểm tra \(prime[i]\) có \(true\) hay không ,ta sẽ đi gán \(prime[9]=prime[12]=false\). Rõ ràng ta thấy có sự lặp lại ở bài toán \(1\). Do đó việc kiểm tra ngay từ ban đầu \(prime[i]\) có \(true\) hay không là việc làm hữu ích, giúp ta loại bỏ được những trường hợp lặp so với bài toán \(1\), và lúc này ta chỉ cần gán \(prime[9]=false\), và \(v[3]=1+1=2\).
  • Mọi người có thể xem code của mình tại \(\href{https://ideone.com/lRRVse}{đây}\)
  • Nếu có gì thắc mắc, mọi người cứ comment nhé !
  2 phản hồi