Friday 2 October 2015

FCTRL - Factorial

See on SPOJ

The most important part of a GSM network is so called Base Transceiver Station (BTS). These transceivers form the areas called cells (this term gave the name to the cellular phone) and every phone connects to the BTS with the strongest signal (in a little simplified view). Of course, BTSes need some attention and technicians need to check their function periodically.

ACM technicians faced a very interesting problem recently. Given a set of BTSes to visit, they needed to find the shortest path to visit all of the given points and return back to the central company building. Programmers have spent several months studying this problem but with no results. They were unable to find the solution fast enough. After a long time, one of the programmers found this problem in a conference article. Unfortunately, he found that the problem is so called "Travelling Salesman Problem" and it is very hard to solve. If we have N BTSes to be visited, we can visit them in any order, giving us N! possibilities to examine. The function expressing that number is called factorial and can be computed as a product 1.2.3.4....N. The number is very high even for a relatively small N.

The programmers understood they had no chance to solve the problem. But because they have already received the research grant from the government, they needed to continue with their studies and produce at least some results. So they started to study behaviour of the factorial function.
For example, they defined the function Z. For any positive integer N, Z(N) is the number of zeros at the end of the decimal form of number N!. They noticed that this function never decreases. If we have two numbers N1<N2, then Z(N1) <= Z(N2). It is because we can never "lose" any trailing zero by multiplying by any positive number. We can only get new and new zeros. The function Z is very interesting, so we need a computer program that can determine its value efficiently.


Simply you have to find the number of zero's at the end of N! (factorial(N))


Input

There is a single positive integer T on the first line of input (equal to about 100000). It stands for the number of numbers to follow. Then there are T lines, each containing exactly one positive integer number N, 1 <= N <= 1000000000.

 

Output

For every number N, output a single line containing the single non-negative integer Z(N).

 

Example

Sample Input:
6
3
60
100
1024
23456
8735373
Sample Output:
0
14
24
253
5861
2183837


Solution- count Number of 5's.

 

Yeah, that's it. You just to calculate the number the of 5's in the prime factorization of N!.
This is because it is obvious for any factorial to have more number of 2's than 5's in its prime factorization. Thus every 5 which appears in factorization will get a 2 so that it can be multiplied with it to become 10. And it is pretty clear that the number of occurrences of 10 in factorization is the same as the number of 0's at the end.


Logic-
Suppose we have number 100. we need to calculate the number of 5 in the prime factorization of 100!.

We know 100!=1*2*3*4*5....*100
Let zeros= number of zeros initially zero.


Thus every number divisible by 5 (like 5,10,15..95,100) will give one 5 as a factor.
zeros+=(100/5)=20
Similarly numbers divisible by 5*5=25 (like 25,50, 75,100) will give two 5's as factors.

(Since one five is already taken into account)
zeros+=100/25... =24

Now 5^3=125>N(100) thus we stop here.

And the answer is 24.

Simple C++ Implementation is here . Time Taken =0.01 sec. 



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//zero in factorial


#include <bits/stdc++.h>
 
   int main()
 {int a,zeros,num,i,t,j;
 scanf("%d",&t);
 
while(t--)
 {   
 	scanf("%d",&num);

	  a=5;
	  zeros=0 ;
 		 while(num/a!=0)

			{					

				zeros+=num/a;

				a=a*5;		//increasing a to powers of 5

			}

printf("\n%d",zeros);

}
 
 return 0;
 }

Posted by at No comments:
Labels: , , , , , ,

PALIN - The Next Palindrome

See on SPOJ


A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.

 

Input

The first line contains integer t, the number of test cases. Integers K are given in the next t lines.

 

Output

For each K, output the smallest palindrome larger than K.

 

Example

Input:
2
808
2133
Output:
818
2222

Solution- Trace from Middle. O(n)

This solution is an approach to avoid recursion.
Take the input as an array of characters (or String). Then there will be 2 big cases.
  • The input number is a palindrome and has all 9s. For example “9 9 9″. The output should be “1 0 0 1″. for this, we will just output the string of length 1 greater than the previous with 1 at ends and 0 in middle.
  • Other cases. say 2133
    1. Split it into the left half and right half ("21", "33");
    2. Compare the last digit in the left half and the first digit in the right half.
      a. If the right is greater than the left, increment the left and stop. ("22")
      b. If the right is less than the left, stop.
      c. If the right is equal to the left, repeat step 3 with the second-last digit in the left and the second digit in the right (and so on).
    3. Take the left half and append the left half reversed. That's your next largest palindrome. ("2222")

Applied to a more complicated  Even length number:
1.    1234567887654322
2.    12345678   87654322
3.    12345678   87654322
             ^   ^         equal
3.    12345678   87654322
            ^     ^        equal
3.    12345678   87654322
           ^       ^       equal
3.    12345678   87654322
          ^         ^      equal
3.    12345678   87654322
         ^           ^     equal
3.    12345678   87654322
        ^             ^    equal
3.    12345678   87654322
       ^               ^   equal
3.    12345678   87654322
      ^                 ^  greater than, so increment the left

3.    12345679

4.    1234567997654321  answer

Applied to a more complicated ODD length number:
1.    12345678987654322
2.    12345678 9 87654322
3.    12345678 9 87654322
             ^   ^         equal
3.    12345678 9 87654322
            ^     ^        equal
3.    12345678 9 87654322
           ^       ^       equal
3.    12345678 9 87654322
          ^         ^      equal
3.    12345678 9 87654322
         ^           ^     equal
3.    12345678 9 87654322
        ^             ^    equal
3.    12345678 9 87654322
       ^               ^   equal
3.    12345678 9 87654322
      ^                 ^  greater than, so increment the middle,
                           but middle is max (9) here so make it zero 
                           and increment the next closer digits on both sides(8)
 
 3.    12345679 0 97654321 and make second half same.

4.    12345679097654321  answer
 


Implementation in C++. Time taken is 0.08 sec.


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
//next palindrome



#include <bits/stdc++.h>
 
    #define max1(x,y) (x)>(y)?(x):(y)
     
    #define s(n) scanint(n)
    #define sc(n) scanf(" %c",&n)
     #define sl(n) scanf("%ld",&n)
    #define sll(n) scanf("%lld",&n)
    #define sf(n) scanf("%lf",&n)
    #define ss(n) scanf("%s",n)
    #define INF (int)1e9
    #define EPS 1e-9
    #define bitcount __builtin_popcount
    #define gcd __gcd
    #define forall(i,a,b) for(int i=a;i<b;i++)
    #define all(a) a.begin(), a.end()
    #define pb push_back
    #define sz(a) ((int)(a.size()))
    #define mp make_pair
    #define checkbit(n,b) ( (n >> b) & 1)
    #define gc getchar_unlocked
    #define l long
  
    using namespace std ;

    inline void scanint(int &x)
    {
    register int c = gc();
    x = 0;
    int neg = 0;
    for(;((c<48 || c>57) && c != '-');c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
    }
    

    int all_nine(string str)  //check if all digits are '9' 
    {
        for(int i=0;i<str.length();i++)
        {
            if(str[i]!='9')
                return 0;
        }
        return 1;
    }
     
    int main()
    {
        string str;
        int t;
        s(t);
        
        while(t--){
        cin>>str;
        int i,j,num;
        char ans[str.length()+3];
        int n=str.length();
        
        if(all_nine(str))
        {                       //if all 9
            ans[0]='1';
            for(i=0;i<n;i++)   
            {
                ans[i+1]='0';
            }
            ans[n]='1';
            ans[n+1]='\0';
            cout<<ans<<endl;
        }
        
        else
        {
            i=n/2;
            j=i;
     
            if(n%2==0)  
            i=i-1;
     
            while(i>=0 && str[i]==str[j])
            {                   //checking for equal from middle
                                // <---i    j--->           
                i--;
                j++;
            }
     
            if(i<0 || str[i]<str[j])
            {                   //not equal or string is palindroic(i<0)
                i=n/2;
                j=i;
                if(n%2==0)
                    i=i-1;
            int carry=1;
            while(i>=0)
            {
                num=((str[i]-'0')+carry);
                carry=num/10;
                str[i]=(num%10)+'0';
                str[j]=str[i];
                i--;
                j++;
            }
            }
            else
            {
                while(i>=0)     //making second half same.
                    {
                        str[j]=str[i];
                        i--;
                        j++;
                    }
            }
            cout<<str<<endl;
        }
        
        }
        return 0;
    }

Posted by at 13 comments:
Labels: , , , , ,

ONP - Transform the Expression

See on SPOJ

Transform the algebraic expression with brackets into RPN form (Reverse Polish Notation). Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,...,z. Assume that there is only one RPN form (no expressions like a*b*c).  



In simple words, convert an infix expression to postfix.

Input

t [the number of expressions <= 100]
expression [length <= 400]
[other expressions]
 
Text grouped in [ ] does not appear in the input file.

 

Output

The expressions in RPN form, one per line.

 

Example

Input:
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

Output:
abc*+
ab+zx+*
at+bac++cd+^*
 
 

 Solution- Using Stack.


It uses a stack which is used to hold operators rather than numbers. The purpose of the stack is to reverse the order of the operators in the expression. It also serves as a storage structure, since no operator can be printed until both of its operands have appeared.
In this algorithm, all operands are printed (or sent to output) when they are read. There are more complicated rules to handle operators and parentheses.

Example 
A * (B + C) becomes A B C + *
A subexpression in parentheses must be done before the rest of the expression.

current symbol operator stack postfix string
1
 A A
2
 * * A
3
 ( * ( A B
4
 B * ( A B
5
 + * ( + A B
6
 C * ( + A B C
7
 ) * A B C +
8
 A B C + *
Since expressions in parentheses must be done first, everything on the stack is saved and the left parenthesis is pushed to provide a marker. When the next operator is read, the stack is treated as though it were empty and the new operator (here the '+' sign) is pushed on. Then when the right parenthesis is read, the stack is popped until the corresponding left parenthesis is found. Since postfix expressions have no parentheses, the parentheses are not printed.

Here is the code to implement this. Time taken 0.00 sec.


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
//infix to postfix
//stack

#include <bits/stdc++.h>
 
    #define max1(x,y) (x)>(y)?(x):(y)
     
    #define s(n) scanint(n)
    #define sc(n) scanf(" %c",&n)
     #define sl(n) scanf("%ld",&n)
    #define sll(n) scanf("%lld",&n)
    #define sf(n) scanf("%lf",&n)
    #define ss(n) scanf("%s",n)
    #define INF (int)1e9
    #define EPS 1e-9
    #define bitcount __builtin_popcount
    #define gcd __gcd
    #define forall(i,a,b) for(int i=a;i<b;i++)
    #define all(a) a.begin(), a.end()
    #define pb push_back
    #define sz(a) ((int)(a.size()))
    #define mp make_pair
    #define checkbit(n,b) ( (n >> b) & 1)
    #define gc getchar_unlocked
    #define l long
  
    using namespace std ;

    inline void scanint(int &x)
    {
    register int c = gc();
    x = 0;
    int neg = 0;
    for(;((c<48 || c>57) && c != '-');c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
    }
  // Function to convert Infix expression to postfix 
string InfixToPostfix(string expression);

// Function to verify whether an operator has higher precedence over other
int HasHigherPrecedence(char operator1, char operator2);

// Function to verify whether a character is operator symbol or not. 
bool IsOperator(char C);

// Function to verify whether a character is alphanumeric chanaracter (letter or numeric digit) or not. 
bool IsOperand(char C);

int main() 
{
 string expression; 
 
 int t;
 s(t);
 while(t--){
 getline(cin,expression);
 string postfix = InfixToPostfix(expression);
 cout<<postfix<<"\n";
 }
}

// Function to evaluate Postfix expression and return output
string InfixToPostfix(string expression)
{
 // Declaring a Stack from Standard template library in C++. 
 stack<char> S;
 string postfix = ""; // Initialize postfix as empty string.
 for(int i = 0;i< expression.length();i++) {

  // Scanning each character from left. 
  // If character is a delimitter, move on. 
  if(expression[i] == ' ' || expression[i] == ',') continue; 

  // If character is operator, pop two elements from stack, perform operation and push the result back. 
  else if(IsOperator(expression[i])) 
  {
   while(!S.empty() && S.top() != '(' && HasHigherPrecedence(S.top(),expression[i]))
   {
    postfix+= S.top();
    S.pop();
   }
   S.push(expression[i]);
  }
  // Else if character is an operand
  else if(IsOperand(expression[i]))
  {
   postfix +=expression[i];
  }

  else if (expression[i] == '(') 
  {
   S.push(expression[i]);
  }

  else if(expression[i] == ')') 
  {
   while(!S.empty() && S.top() !=  '(') {
    postfix += S.top();
    S.pop();
   }
   S.pop();
  }
 }

 while(!S.empty()) {
  postfix += S.top();
  S.pop();
 }

 return postfix;
}

// Function to verify whether a character is english letter or numeric digit. 
// We are assuming in this solution that operand will be a single character
bool IsOperand(char C) 
{
 if(C >= '0' && C <= '9') return true;
 if(C >= 'a' && C <= 'z') return true;
 if(C >= 'A' && C <= 'Z') return true;
 return false;
}

// Function to verify whether a character is operator symbol or not. 
bool IsOperator(char C)
{
 if(C == '+' || C == '-' || C == '*' || C == '/' || C== '^')
  return true;

 return false;
}

// Function to verify whether an operator is right associative or not. 
int IsRightAssociative(char op)
{
 if(op == '^') return true;
 return false;
}

// Function to get weight of an operator. An operator with higher weight will have higher precedence. 
int GetOperatorWeight(char op)
{
 int weight = -1; 
 switch(op)
 {
 case '+':
 case '-':
  weight = 1;
 case '*':
 case '/':
  weight = 2;
 case '^':
  weight = 3;
 }
 return weight;
}

// Function to perform an operation and return output. 
int HasHigherPrecedence(char op1, char op2)
{
 int op1Weight = GetOperatorWeight(op1);
 int op2Weight = GetOperatorWeight(op2);

 // If operators have equal precedence, return true if they are left associative. 
 // return false, if right associative. 
 // if operator is left-associative, left one should be given priority. 
 if(op1Weight == op2Weight)
 {
  if(IsRightAssociative(op1)) return false;
  else return true;
 }
 return op1Weight > op2Weight ?  true: false;
}


If there is another solution (without stack) please let us know. You will be given credit.
Posted by at 2 comments:
Labels: , , , , , ,

Thursday 1 October 2015

PRIME1 - Prime Generator


See on SPOJ


Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

 

Input

The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

 

Output

For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

 

Example

Input:
2
1 10
3 5

Output:
2
3
5
7

3
5
 

First Solution- Brute Force

 

Yeah, Brute force works too. Though the given constraints are large enough to fail this method, But if you implement it smartly, it will work.
Just check for every number in the range with the check prime() method and print it.

NOTE: This Solution is not recommended. But due to nonexhaustive test cases, it gets through with Time 0.93 sec. 

The Trick behind this is to use as less memory as you can, thus all operation takes place in cache hence runs really fast. 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#include<math.h>
#include<stdio.h>
using namespace std;
 
bool checkprime (long int num)
{
    if (num <=1)
        return false;
    else if (num == 2)        
        return true;
    else if (num % 2 == 0)
        return false;
    else
    {
        bool prime = true;
        int divisor = 3;
      
        int upperLimit =sqrt(num) +1;
        
        while (divisor <= upperLimit)
        {
            if (num % divisor == 0)
                return false;
            divisor +=2;
        }
        return prime;
    }
}
     
 int main()
 {int a,b,i,n,j;
 scanf("%d",&n);
 
 for(i=0;i<n;i++)
 {   
  scanf(" %d %d",&a,&b);
  printf("\n");
  for(j=a;j<=b;j++)
  {            if(checkprime(j))
     printf("%d\n",j);
        
  }
 }
 return 0;
 } 
  









 



Second Solution- Segmented Sieve Of Eratosthenes










The primes need to be found using the Sieve Of Eratosthenes. However, that is also not enough. The traditional Sieve of Eratosthenes gives us the list of prime numbers till a number N. Here we need to find the prime numbers between M and N.So we need a modified form of Sieve of Eratosthenes which works on the same basic principle but only finds the primes within a range called Segmented Sieve Of Eratosthenes. Go ahead at this point, check out the Wikipedia article on these subjects.







Logic:

We know that 2 is the first prime no. So, if we start from 2(excluding 2) and increment in 2 steps(that is i=i+2) all numbers we get are divisible by 2 at least. So they cannot be prime.So
 all those numbers we remove from the list(here removal from the list is done by making segment[]=true for that number). Then the next bigger number that is still on the list will surely be a prime number. In our case, it is 3.  3 is a prime number. We start from 3 and increment in steps of 3, we cut-off 6,9,12, and so on. After
 2 and 3, the next largest number in the list that has not been removed is 5. Since 4 has only been cut off as it is a composite of 2. We cut 
10,15,20 and so on till N.In this way we remove composite numbers and after a while, the list contains only prime numbers.



Segmented Sieve

Say I need to find the prime numbers between 125 and 140. One way is to find all primes till 140 using traditional sieves and then find how many of them are greater than 125. This will not work within limited time constraints. We need to fit the Sieve to our needs so that we run the Sieve only in that particular range.



The first prime is 2.We divide the starting number x=125 by 2.We 
round off to smaller integer we get 62. We again multiply by 2 we get 
124. What is 124? it is the first smaller number than x that is divisible by the prime 2.We start from 124, increment by 2 in each step, and remove all elements between 125 and 140. That is we remove 
126,128,130,132,134,136,138,140.What we did was that we did the first step in a traditional sieve but just offset the starting elements to the closest composite number less than the starting point of the range. Next,
 we do this with the 2nd smallest prime number 3.125/3=41.41*3=123.We 
start from 123 go till 140 (inclusive) in steps of 3 and cut the numbers
 126,129,132,135,138.Next, we do with 5. But from where do we get the prime numbers 2,3,5 and so on and how long do we need to do that?



We must first use a traditional sieve to make a list of primes up to sqrt(N) where N is the larger of the range. Then we will use this list of primes in the segmented sieve operation. This will leave us with the prime numbers in the desired range. Please re-read the above part a number of times and get this concept clear or revert back in case of any query.







The Trick behind this is to use as less memory as you can, thus all operation takes place in cache hence runs really fast. If you increase the segment size then it may give TLE.





This method Decreases the time taken to 0.01 sec.












  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123


//generate Prime using sieve
//segmented sieve
//limits the memory used, thus inside cache only hence speed up 


    #include <bits/stdc++.h>
 
    #define max1(x,y) (x)>(y)?(x):(y)
     
    #define s(n) scanint(n)
    #define sc(n) scanf(" %c",&n)
    #define sl(n) scanf("%ld",&n)
    #define sll(n) scanf("%lld",&n)
    #define sf(n) scanf("%lf",&n)
    #define ss(n) scanf("%s",n)
    #define INF (int)1e9
    #define EPS 1e-9
    #define bitcount __builtin_popcount
    #define gcd __gcd
    #define forall(i,a,b) for(int i=a;i<b;i++)
    #define all(a) a.begin(), a.end()
    #define pb push_back
    #define sz(a) ((int)(a.size()))
    #define mp make_pair
    #define checkbit(n,b) ( (n >> b) & 1)
    #define gc getchar_unlocked
    #define l long
  
    using namespace std ;

    inline void scanint(int &x)
    {
    register int c = gc();
    x = 0;
    int neg = 0;
    for(;((c<48 || c>57) && c != '-');c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
    }


   vector<int > primeArray;

    bool check[50009];

    int keep = 1;


    void initialise()
    {
        check[1 ] = 1;
        for(int i = 3 ; i <=224 ; i+=2){
            if(!check[i]){
                for(int j = i*i ; j<= 50000 ; j+=2*i)
                    check[j] = true;
            }
        }
        primeArray.pb(2);
        keep=1;
        for(int i = 3 ; i<= 50000 ; i++)
            if(check[i] == false && (i&1))
                primeArray.pb(i) , keep++;
    }


    bool segment[1000009];



    int main()
    {
        int t;
        s(t);
        initialise();
        while(t--)
        {
            int a , b;
            s(a),s(b);

            if(b <= 50000){
                if(a<=2)
                    printf("2\n");
                for(int i = a ; i<= b ; i++){
                    if(check[i] == false && (i&1))
                        printf("%d\n", i);
                }
                continue;
            }

            memset(segment , 0 , sizeof segment);


            for(int i = 0; primeArray[i]*primeArray[i] <= b ; i++)
            {
                int begin = a/primeArray[i];
                begin *= primeArray[i];
                for(int j = begin ; j<= b ; j+= primeArray[i]){
                    if(j < a)
                        continue;
                    segment[j - a] = true;
                }
            }

            for(int i  = 0 ; primeArray[i]*primeArray[i] <= b ; i++){
                if(primeArray[i]>= a && primeArray[i]<=b)
                    printf("%d\n",primeArray[i]);
            }

            for(int i = a==1?1:0 ; i < b-a+1 ; i++)
                if(segment[i]==0)
                    printf("%d\n", i+a);
        }

        return 0;
    }



























Posted by



at





1 comment:
  


















Labels:
,
,
,
,
,

















        

      









Subscribe to:
Posts (Atom)