Chef and Magical Steps CodeChef Solution

Problem -Chef and Magical Steps CodeChef Solution

“ ”

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.

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";
    }
    
	// your code goes here
	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 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    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;
        }
        int testcase = Integer.parseInt(br.readLine());
        while(testcase-->0){
            st = new StringTokenizer(br.readLine());
            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 *
inp = lambda: sys.stdin.buffer.readline().decode().strip()
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();
            int testCases = sc.ReadInt();
            while (testCases-- > 0)
            {
                long[] nk = sc.ReadLongArr();
                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 StreamReader streamReader = new StreamReader(Console.OpenStandardInput());
        public static StreamWriter streamWriter = new StreamWriter(Console.OpenStandardOutput());
#else
        public static StreamReader streamReader = new StreamReader(@"C:\Users\869963\Documents\Coding\C#\input.txt");
        public static StreamWriter streamWriter = new StreamWriter(@"C:\Users\869963\Documents\Coding\C#\output.txt");
#endif
        #region Input
        public int ReadInt()
        {
            return Convert.ToInt32(streamReader.ReadLine());
        }
        public string ReadLine()
        {
            return streamReader.ReadLine();
        }
        public long ReadLong()
        {
            return Convert.ToInt64(streamReader.ReadLine());
        }
        public double ReadDouble()
        {
            return Convert.ToDouble(streamReader.ReadLine());
        }
        public int[] ReadIntArr()
        {
            return ConvertAll(streamReader.ReadLine().TrimEnd().Split(' '), t => Convert.ToInt32(t));
        }
        public float[] ReadFloatArr()
        {
            return ConvertAll(streamReader.ReadLine().TrimEnd().Split(' '), t => float.Parse(t));
        }
        public long[] ReadLongArr()
        {
            return ConvertAll(streamReader.ReadLine().TrimEnd().Split(' '), t => Convert.ToInt64(t));
        }
        public char[] ReadCharArr()
        {
            return streamReader.ReadLine().ToCharArray();
        }
        public int[][] ReadInt2DArr(long n)
        {
            int[][] res = new int[n][];
            for (int i = 0; i < n; i++)
            {
                res[i] = ReadIntArr();
            }
            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()
        {
            streamReader.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() {
	reader := bufio.NewReader(os.Stdin)

	tc := readNum(reader)

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

	fmt.Print(buf.String())
}

func readNInt64s(reader *bufio.Reader, n int) []int64 {
	res := make([]int64, n)
	s, _ := reader.ReadBytes('\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
	var sign int64 = 1
	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
}

func readNum(reader *bufio.Reader) (a int) {
	bs, _ := reader.ReadBytes('\n')
	readInt(bs, 0, &a)
	return
}

func readTwoNums(reader *bufio.Reader) (a int, b int) {
	res := readNNums(reader, 2)
	a, b = res[0], res[1]
	return
}

func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
	res := readNNums(reader, 3)
	a, b, c = res[0], res[1], res[2]
	return
}

func readNNums(reader *bufio.Reader, n int) []int {
	res := make([]int, n)
	x := 0
	bs, _ := reader.ReadBytes('\n')
	for i := 0; i < n; i++ {
		for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
			x++
		}
		x = readInt(bs, x, &res[i])
	}
	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!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn