sieve of eratosthenes - SPOJ Prime generator Wrong Answer -


here link problem-:http://www.spoj.com/problems/prime1/. problem asks find prime numbers between given rang 1 <= m <= n <= 1000000000, n-m<=100000. have implemented segmented sieve here logic-: problem has maximum value of 10^9, find primes withing square_root(10^9) around 31622.

#include<iostream> #include<cstdio> #include<cmath> using namespace std;  void prime1(long int low, long int high, bool* pre) {     bool prime[high-low+1]={0};      if(low==high)         {if(pre[low]==0)printf("%ld\n", low);return;}     int t=sqrt(high);     for(long int i=2;i<=t;i++)     {         if(pre[i]==1)continue;         long int a=ceil(((double)low/i))*i;// start value         long int b=floor(((double)high/i))*i;// end value         if(a==1)             continue;         if(a==i)             a+=i;         if(a==0)             a=2*i;         for(long int x=a;x<=high;x+=i)         {             prime[x-low]=1;         }     }     if(low==1)         prime[0]=1;     else if(low==0)         prime[0]=prime[1]=1;     for(int i=0;i<=(high-low);i++)         if(!prime[i])printf("%ld\n", i+low); } int main() {      bool pre[32001];     pre[0]=pre[1]=1;      int x=sqrt(32001);     for(int i=2;i<=x;i++)     {         if(pre[i]==0)         {             for(int j=i;i*j<=32000;j++)             {                 pre[i*j]=1;             }         }     }      int t;      scanf("%d",&t);     long low, high;     while(t--)     {         scanf("%ld %ld",&low, &high);         printf("\n")         prime1(low, high, pre);      } }

now i'll start i=2 , find multiples between m , n. here m , n represent low , high respectively. i'll keep on increasing till i<=sqrt(n) example, m=125 , n=140 a=((double)m/i)*i. i'll consider ceiling value. so, when m=125 i=2 a=126. so, 126+(2*k) composite k>=0. same i=3,5,7.....

when submit on spoj, gives me wa. have used spoj toolkit contained test cases. compared other code , getting same result. missing?


Comments

Post a Comment

Popular posts from this blog

php - Vagrant up error - Uncaught Reflection Exception: Class DOMDocument does not exist -

i've set bento/ubuntu-16.04 vagrant box using php 5.6, , getting following error quite few times when try , run shell script: "uncaught reflection exception: class domdocument not exist". i've tried adding following top of script (not together), each no success: "sudo apt-get install php5.6-xml", "sudo apt-get install php5-xml", "sudo apt-get install php-dom" i've tried resetting server "sudo service apache2 restart". does have suggestions?
Read more

vue.js - Create hooks for automated testing -

Image
qa guys complained can't automate frontend testing. because our html looks same outside. lazy hack did this <template> <div :role="$options.name"> ... </div> </template> <script> export default { name: 'vmcomponentname' } </script> which takes name script , applies html. in browser get: <div role="vmcomponentname"> ... </div> line :role="$options.name" goes in every component. is there dry er solutions? please share. additional details i'll explain in details looking for. imagine have vmusercreate form creates user. test case can create user . to automatically test without role, have use following selector: .wrapper > .wrapper > .wrapper > .submit-button the test extremely brittle (will break lot). if use roles can use [role="vmusercreateform"] .submit-button selector. many folds less brittle. so basically, i'm ...
Read more

Add new key value to json node in java -

i have json file : { "id":1, "name":"abc", "addressdetails": { "city":"newyork" } } i wanted add 1 more key-value ("pincode" : "414141") node 'addressdetails'. i tried using : objectmapper mapper = new objectmapper(); jsonnode root = mapper.readtree(new file("d://test.json")); objectnode node = mapper.createobjectnode(); node.with("addressdetails").put("pincode", "414141"); but it's not getting added, there way can ? you can try you should modify file path objectmapper mapper = new objectmapper(); objectnode nodes = mapper.readvalue(new file("d:\\test.txt"), objectnode.class); nodes.with("addressdetails").put("pincode", "414141"); mapper.writer().writevalue(new file("d:\\test.txt"), nodes);
Read more