Skip to content
The Chat Archive
o1-mini-2024-09-12· OpenAI WildChat-4.8M (AI2)

Problem B: Prime Subtractorization 18 points Validate Solution & Submit Problem My…

  1. User

    Problem B: Prime Subtractorization 18 points

    Validate Solution & Submit Problem My Submissions A prime number is an N N-subtractorization if it can be expressed as the difference of two primes that are both at most N N. For example, the complete set of 5 5-subtractorizations is { 2 , 3 } {2,3} because 5 − 3

    2 5−3=2 and 5 − 2

    3 5−2=3. For a given N N, how many N N-subtractorizations are there? Constraints 1 ≤ T ≤ 100 1≤T≤100 1 ≤ N ≤ 10 , 000 , 000 1≤N≤10,000,000 Input Format Input begins with an integer T T, the number of test cases. Each case is a single line that contains the integer N N. Output Format For the i ith test case, print "Case #i: " followed by a single integer, the number of N N-subtractorizations. Sample Explanation The first case is explained above. In the second case, the complete set of 8 8-subtractorizations is { 2 , 3 , 5 } {2,3,5}. Sample Input 2 5 8 Sample Output Case #1: 2 Case #2: 3 solve this task in c++. use <bits/std... use no comments also use naming at max 3 letters

  2. Assistant
    #include<bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        int T; cin>>T;
        vector<int> Ns(T); int M=0; for(auto &x:Ns){cin>>x; M = max(M, x);}
        vector<bool> sieve(M+2, true); sieve[0]=sieve[1]=false;
        for(int i=2;i*i<=M;i++) if(sieve[i]){
            for(int j=i*i;j<=M;j+=i) sieve[j]=false;
        }
        vector<int> prs; for(int i=2;i<=M;i++) if(sieve[i]) prs.push_back(i);
        int tc=1;
        for(auto N:Ns){
            int cnt=0;
            for(auto p:prs){
                if(p > N) break;
                // Find r <=N -p
                // Iterate r in prs until r > N -p
                for(auto r:prs){
                    if(r > N -p) break;
                    if(sieve[p + r]){
                        cnt++; break;
                    }
                }
            }
            cout<<"Case #"<<tc++<<": "<<cnt<<"\n";
        }
    }