304 North Cardinal St.
Dorchester Center, MA 02124

# Chef and Magical Steps CodeChef Solution

## Chef and Magical Steps CodeChef Solution in C++17

``````#include <bits/stdc++.h>
typedef int ll;
#define ld long double
#define pb push_back
/* You may enter other macros defined by you */
#define vi vector<ll>
#define sortA(v) sort(v.begin(),v.end())
#define sortD(v) sort(v.begin(),v.end(), greater<ll>())
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define ff first
#define ss second
#define pll pair<ll, ll>
#define vll vector<ll>
#define printv(a) for(auto x: a){cout<<x<<" ";}cout<<"\n";
#define input(a,n) rep(i,n)cin>>a[i];
#define input1(a,n) rep1(i,n)cin>>a[i];

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define minv(a) *min_element(all(a))
#define maxv(a) *max_element(all(a))
using namespace std;

const int MOD = 1e9+7;
//const int MOD = 998244353;
const ld PI = acos(-1);
const ld EPS = 1e-9;

const ll N = 1e7;
vector<ll> lp(N+1);
vector<ll> pr;

void linear_sieve(){
for (ll i=2; i <= N; ++i) {
if (lp[i] == 0) {
lp[i] = i;
pr.push_back(i);
}
for (ll j = 0; i * pr[j] <= N; ++j) {
lp[i * pr[j]] = pr[j];
if (pr[j] == lp[i]) {
break;
}
}
}
}

void solve(){
ll x,y;cin>>x>>y;
auto it1 = lower_bound(all(pr),x+2);
auto it2 = lower_bound(all(pr),y+1);
cout<<  y-x - (it2 - it1)<<endl;
}

int main(){

ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t;
cin>>t;
linear_sieve();
rep1(i,t){
solve();
}
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";

return 0;
}``````

## Chef and Magical Steps CodeChef Solution in C++14

``````#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);

const int MAX=1e7+1;
bool v[MAX];
int len, sp[MAX];

void Sieve(){
for (int i = 2; i < MAX; i += 2)	sp[i] = 2;//even numbers have smallest prime factor 2
for (ll i = 3; i < MAX; i += 2){
if (!v[i]){
sp[i] = i;
for (ll j = i; (j*i) < MAX; j += 2){
if (!v[j*i])	v[j*i] = true, sp[j*i] = i;
}
}
}
}

int main() {

fast;
Sieve();

vector<int>dp(1e7,0);
for(int i=1;i<MAX;i++){
if(sp[i]==i)dp[i]=dp[i-1]+1;
else dp[i]=dp[i-1];
}

int t;
cin>>t;
while(t--){

int x,y;
cin>>x>>y;
int num_prime=dp[y]-dp[x+1];
int ans=y-x-num_prime;
cout<<ans<<"\n";
}

return 0;
}``````

## Chef and Magical Steps CodeChef Solution in PYTH 3

``````# cook your dish here
#list(map(int,input().split()))
#map(int,input().split())
maxN=10000009
prime=[1 for i in range(maxN+1)]
i=2
while i*i<=maxN:
if prime[i]:
for j in range(i**2,maxN+1,i):
prime[j]=False
i+=1
prime[0],prime[1]=[0]*2
for i in range(1,maxN+1):
prime[i]+=prime[i-1]
for _ in range(int(input())):
x,y=map(int,input().split())
cnt=0
print(y-x-(prime[y]-prime[x+1]))``````

## Chef and Magical Steps CodeChef Solution in C

``````#include<stdio.h>
#include<math.h>
#define ll long long int
ll prime[10000001];
ll prefix[10000001];

void primesmallerthanN(int n){
ll p,j;
for(j=0;j<=n;++j)
prime[j] = 1;
prime[1] = 0;
for(p=2;p<=sqrt(n);++p){
for(j=p*p;j<=n;j+=p){
prime[j] = 0;
}
}
}
int main() {
primesmallerthanN(10000000);
ll i;
for(i=2;i<=10000000;++i){
prefix[i] = prime[i] + prefix[i-1];
}
ll t;
scanf("%lld",&t);
while(t--){
ll l,r;
scanf("%lld",&l);
scanf("%lld",&r);
ll p =(prefix[r]-prefix[l+1]);
printf("%lld",((r-l)-p));
printf("\n");
}
}``````

## Chef and Magical Steps CodeChef Solution in JAVA

``````import java.util.*;
import java.io.*;
class CodeChef{

static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static StringTokenizer st = null;

public static void main(String[] args)throws IOException {

int[] primes = new int[10000001];

boolean[] p = new boolean[10000001];
int count = 0;
for(int i=2;i<10000001;i++){
if(!p[i]){
count++;
for(int j=i;j<10000001;){
p[j] = true;
j+=i;
}
}
primes[i] = count;
}
while(testcase-->0){
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int cnt = primes[m] - primes[n+1];
pw.println((m-n-cnt));

}

pw.close();
}
}``````

## Chef and Magical Steps CodeChef Solution in PYPY 3

``````import sys
from math import *
from collections import *
from bisect import *
out=sys.stdout.write
# n=int(inp())
# arr=list(map(int,inp().split()))
MAX=10**7+7
is_prime=[1]*MAX
is_prime[0],is_prime[1]=0,0
def Sieve(n):
global is_prime
p = 2
while (p * p <= n):
if (is_prime[p] == 1):
for i in range(p * p, n+1, p):
is_prime[i] = 0
p += 1
Sieve(MAX-2)
mmax=MAX-1
arr=[0,1]
i=0
while i<mmax:
if i+2<mmax and is_prime[i+2]:
arr.append(i+2)
i+=2
elif i+1<mmax:
arr.append(i+1)
i+=1
else:
i+=1
arr=arr[:2]+arr[3:]
# print(arr[:50])
for _ in range(int(inp())):
x,y=map(int,inp().split())
if y==2:
out(str(1)+"\n")
continue
idx1,idx2=bisect_left(arr,x),bisect_left(arr,y)
# print(idx1,idx2)
if arr[idx1]!=x:
out(str(idx2-idx1+1)+"\n")
else:
out(str(idx2-idx1)+"\n")``````

## Chef and Magical Steps CodeChef Solution in PYTH

``````from bisect import bisect_left, bisect
def primes(n):
sieve = [True] * n
for i in xrange(3,int(n**0.5)+1,2):
if sieve[i]:
sieve[i*i::2*i]=[False]*((n-i*i-1)/(2*i)+1)
return [2] + [i for i in xrange(3,n,2) if sieve[i]]
p = primes(10000000)
for _ in xrange(input()):
x, y = map(int, raw_input().split())
a = bisect_left(p, x+2)
b = bisect(p, y)
print y - x  - (b - a)``````

## Chef and Magical Steps CodeChef Solution in C#

``````#region usings
using System;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections;
using static System.Math;
using static System.Array;
using static System.Convert;
using System.Collections.Generic;
using System.Runtime.CompilerServices;

#endregion
namespace CodeChef
{
public class Solution
{
private static readonly Scanner sc = new Scanner();
static int MAX = 10000000;
static int[] prefix = new int[MAX + 1];
static void BuildPrefix()
{
bool[] prime = new bool[MAX + 1];

for (int p = 2; p * p <= MAX; p++)
{
if (prime[p] == false)
{
for (int i = p * 2; i <= MAX; i += p)
prime[i] = true;
}
}
prefix[0] = prefix[1] = 0;
for (int p = 2; p <= MAX; p++)
{
prefix[p] = prefix[p - 1];
if (prime[p] == false)
prefix[p]++;
}
}
static int Query(int L, int R)
{
return prefix[R] - prefix[L];
}
static void Main()
{
BuildPrefix();
while (testCases-- > 0)
{
Solve(nk);
}
sc.Flush();
sc.Close();
}
private static void Solve(long[] nk)
{
long a = nk[0], b = nk[1];
var temp = Query((int)nk[0] + 1, (int)nk[1]);
if (a == 1 && b == 2)
{
sc.WriteLine("1");
return;
}
else if (a == 1 && b == 3)
{
sc.WriteLine("2");
return;
}
else if (a == 2 && b == 3)
{
sc.WriteLine("1");
return;
}
sc.WriteLine(b - a - temp);

}
}
public class Scanner
{

#if (!DEBUG)
public static StreamWriter streamWriter = new StreamWriter(Console.OpenStandardOutput());
#else
public static StreamWriter streamWriter = new StreamWriter(@"C:\Users\869963\Documents\Coding\C#\output.txt");
#endif
#region Input
{
}
{
}
{
}
{
}
{
}
{
}
{
}
{
}
{
int[][] res = new int[n][];
for (int i = 0; i < n; i++)
{
}
return res;
}
#endregion
#region Output
public void Write<T>(T t)
{
streamWriter.Write(t);
}
public void WriteLine<T>(T result)
{
streamWriter.WriteLine(result);
}
public void Write2DMatrix<T>(T[,] sum, int n, int m)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
Write<string>(\$"{sum[i, j]}");
}
WriteLine<string>("");
}
}
public void YESNO(bool condition)
{
WriteLine(condition ? "YES" : "NO");
}
public void YesNo(bool condition)
{
WriteLine(condition ? "Yes" : "No");
}
public void yesno(bool condition)
{
WriteLine(condition ? "yes" : "no");
}
public void Flush()
{
streamWriter.Flush();
}
public void Close()
{
streamWriter.Close();
}
internal void WriteArray(long[] secondHalf)
{
for (int i = 0; i < secondHalf.Length; i++)
{
streamWriter.WriteLine(secondHalf[i] + " ");
}
WriteLine("");
}
#endregion
}
public class Utilities
{
public static long GCD(long a, long b)
{
if (b == 0)
return a;
return GCD(b, a % b);
}
public static long LCM(long a, long b)
{
return (a / GCD(a, b)) * b;
}
public static long[] SieveOfEratosthenes(int n)
{
bool[] prime = new bool[n + 1];
long j = 0; long[] arr = new long[n];
for (int i = 0; i < n; i++)
prime[i] = true;

for (int p = 2; p * p <= n; p++)
{
if (prime[p] == true)
{
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
for (int i = 2; i <= n; i++)
{
if (prime[i] == true)
{
arr[j] = i;
j++;
}
}
return arr;
}
}
}``````

## Chef and Magical Steps CodeChef Solution in GO

``````package main

import (
"bufio"
"bytes"
"fmt"
"os"
)

func main() {

var buf bytes.Buffer
for tc > 0 {
tc--
res := solve(X, Y)
buf.WriteString(fmt.Sprintf("%d\n", res))
}

fmt.Print(buf.String())
}

res := make([]int64, n)

var pos int

for i := 0; i < n; i++ {
pos = readInt64(s, pos, &res[i]) + 1
}

return res
}

func readInt64(bytes []byte, from int, val *int64) int {
i := from
if bytes[i] == '-' {
sign = -1
i++
}
var tmp int64
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + int64(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}

func readInt(bytes []byte, from int, val *int) int {
i := from
sign := 1
if bytes[i] == '-' {
sign = -1
i++
}
tmp := 0
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}

return
}

a, b = res[0], res[1]
return
}

a, b, c = res[0], res[1], res[2]
return
}

res := make([]int, n)
x := 0
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
}
return res
}

func readUint64(bytes []byte, from int, val *uint64) int {
i := from

var tmp uint64
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp

return i
}

const MAX_NUM = 10000010

var primes []int

func init() {
set := make([]bool, MAX_NUM)

for x := 2; x < MAX_NUM; x++ {
if !set[x] {
primes = append(primes, x)
for y := 2 * x; y < MAX_NUM; y += x {
set[y] = true
}
}
}
}

func solve(X, Y int) int {
i := search(len(primes), func(i int) bool {
return primes[i] > Y
})

j := search(len(primes), func(j int) bool {
return primes[j] > X
})

if X+2 > primes[j] {
j++
}

res := Y - X

if j < i && primes[j]+2 <= Y {
res -= (i - j)
}

return res
}

func search(n int, fn func(int) bool) int {
l, r := 0, n
for l < r {
mid := (l + r) / 2
if fn(mid) {
r = mid
} else {
l = mid + 1
}
}
return r
}``````
##### Chef and Magical Steps CodeChef Solution Review:

In our experience, we suggest you solve this Chef and Magical Steps CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Chef and Magical Steps CodeChef Solution.

Find on CodeChef

##### Conclusion:

I hope this Chef and Magical Steps CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!