Jan 2010
1 / 4
Jan 2010
Jan 2010
bmudiam
Jan '10

Hi Everyone,

I have written below program to return the prime numbers between two input numbers. It works fine on my machine. But SPOJ is returning me NZEC error. I think problem could be outofmemoryerror with the boolean array. Can someone, suggest a way to address this issue.

using System;
public class PRIME1
{
    static void Main(string[] args)
    {
        int x = int.Parse(Console.ReadLine());
        int count = x;
        string input;
        int val1;
        int val2;
        int index;
        char[] inputChar;
        while (count > 0)
    {
        input = Console.ReadLine();
        inputChar = input.ToCharArray();
        index = input.IndexOf(' ');
        val1 = int.Parse(new String(inputChar, 0, index));
        val2 = int.Parse(new String(inputChar, index + 1, input.Length-index-1));

        PrintPrimes(val1, val2);
        Console.WriteLine();
        count--;
    }
}

static void PrintPrimes(int p, int q)
{
    int half = (int)Math.Sqrt(q);
    bool[] arr = new bool[q];

    for (int i = 0; i < q; i++)
    {
        arr[i] = true;
    }

    for (int i = 1; i <= half; i++)
    {
        if (arr[i])
        {
            int count = 2;
            for (int j = count*(i+1); j <= q; j = count * (i+1))
            {
                arr[j-1] = false;
                count++;
            }
        }
    }

    for (int i = p-1; i < q; i++)
    {
        if (arr[i])
            Console.WriteLine(i+1);
    }
}
}

Thank you very much.

-- Bala

  • created

    Jan '10

  • last reply

    Jan '10
  • 3

    replies

  • 323

    views

  • 2

    users

TripleM_sof
Jan '10

You are not using the most crucial point in the problem statement; n-m<=100000. Figure out how to use that to decrease the size of your array.

bmudiam
Jan '10

As per your suggestion, I tried as below instead of maintaining the boolean array of q size, but instead of only (p-q) size.

Still it gives NZEC error.

using System;
public class PRIME1
{
    static void Main(string[] args)
    {
        int x = int.Parse(Console.ReadLine());
        int count = x;
        string input;
        int val1;
        int val2;
        int index;
        char[] inputChar;
        while (count > 0)
    {
        input = Console.ReadLine();
        inputChar = input.ToCharArray();
        index = input.IndexOf(' ');
        val1 = int.Parse(new String(inputChar, 0, index));
        val2 = int.Parse(new String(inputChar, index + 1, input.Length-index-1));

        PrintPrimes(val1, val2);
        Console.WriteLine();
        count--;
    }
}

static void PrintPrimes(int p, int q)
{
    int half = (int)Math.Sqrt(q);
    int num = (q - p + 1);
    bool[] arr = new bool[num];

    for (int i = 0; i < num; i++)
    {
        arr[i] = true;
    }

    for (int i = 1; i <= half; i++)
    {
        int count = 2;
        for (int j = count * (i + 1); j <= q; j = count * (i + 1))
        {
            if (j > p)
            {
                arr[j - 1] = false;
            }
            count++;
        }
    }

    for (int i = 0; i < num; i++)
    {
        if (arr[i])
            Console.WriteLine(i+1);
    }
}
}
TripleM_sof
Jan '10

                if (j > p)
                {
                    arr[j - 1] = false;
                }

Well that's not right wink You should be able to edit that loop so you don't have to check if j>p as well; just alter the starting value of j somehow.