SPOJ Prime Generator solution | Solution in C, C++,C# Java, Python, Ruby

SPOJ Prime Generator Solution | Solution in C, C++, C#, Java, Python and in Ruby

Sphere Online Judge Solution  Prime Generator - PRIME1
Sphere Online Judge Main Problem Link - http://www.spoj.com/problems/PRIME1/

Problem Name: SPOJ Problem  Prime Generator - PRIME1
Problem Number : SPOJ Problem Prime Generator Solution  PRIME1
Online Judge : SPOJ Solution
Solution Language : C, CPP, Java, Python, C#, Ruby
Level : Classical

SPOJ Prime Generator Code in C language:

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>

int main() {
    int primes[4000];
    int numprimes = 0;

    primes[numprimes++] = 2;
    for (int i = 3; i <= 32000; i+=2) {
        bool isprime = true;
        int cap = sqrt(i)+1;
        for (int j = 0; j < numprimes; j++) {
            if (primes[j] >= cap) break;
            if (i % primes[j] == 0) {
                isprime = false;
                break;
            }
        }
        if (isprime) primes[numprimes++] = i;
    }

    int T,N,M;
    scanf("%d",&T);

    for (int t = 0; t < T; t++) {
        if (t) printf("\n");
        scanf("%d %d",&M,&N);
        if (M < 2) M = 2;

        int cap = sqrt(N) + 1;

        bool isprime[100001];
        memset(isprime,true,sizeof(isprime));

        for (int i = 0; i < numprimes; i++) {
            int p = primes[i];

            if(p >= cap) break;

            int start;

            if (p >= M) start = p*2;
            else start = M + ((p - M % p) % p);

            for (int j = start; j <= N; j += p) {
                isprime[j - M] = false;
            }
        }

        int start = (M % 2)?M:M+1;

        if (M == 2) {
            printf("2\n");
        }
        for (int i = start; i <= N; i+=2) {
            if (isprime[i-M]) printf("%d\n",i);
        }
    }
    return 0;
}

SPOJ Prime Generator Code in C++ Language:

#include <iostream>
#include <cmath>
#include <vector>
#include <set>
using namespace std;

int main() {
    vector<int> primes;
    primes.push_back(2);

    for (int i = 3; i <= 32000; i+=2) {
        bool isprime = true;
        int cap = sqrt(i) + 1;

        vector<int>::iterator p;
        for (p = primes.begin(); p != primes.end(); p++) {
            if (*p >= cap) break;
            if (i % *p == 0) {
                isprime = false;
                break;
            }
        }
        if (isprime) primes.push_back(i);
    }

    int T,N,M;

    cin >> T;

    for (int t = 0; t < T; t++) {
        if (t) cout << endl;

        cin >> M >> N;
        if (M < 2) M = 2;

        int cap = sqrt(N) + 1;

        set<int> notprime;
        notprime.clear();

        vector<int>::iterator p;
        for (p = primes.begin(); p != primes.end(); p++) {

            if (*p >= cap) break;
            int start;

            if (*p >= M) start = (*p)*2;
            else start = M + ((*p - M % *p) % *p);

            for (int j = start; j <= N; j += *p) {
                notprime.insert(j);
            }
        }

        for (int i = M; i <= N; i++) {
            if (notprime.count(i) == 0) {
                cout << i << endl;
            }
        }

    }
    return 0;
}

SPOJ Prime Generator Code in Java Language:

Hint : Simple code. Just bigger time. But it's awesome

import java.io.*;
import java.util.*;
import java.lang.Math.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int[] primes = new int[4000];
        int numprimes = 0;

        primes[numprimes++] = 2;
        for (int i = 3; i <= 32000; i+=2) {
            boolean isprime = true;
            double cap = Math.sqrt(i) + 1.0;

            for (int j = 0; j < numprimes; j++) {
                if (j >= cap) break;
                if (i % primes[j] == 0) {
                    isprime = false;
                    break;
                }
            }
            if (isprime) primes[numprimes++] = i;
        }


        int T,N,M;

        T = in.nextInt();

        for (int t = 0; t < T; t++) {
            if (t > 0) System.out.println("");

            M = in.nextInt();
            N = in.nextInt();

            if (M < 2) M = 2;

            boolean[] isprime = new boolean[100001];
            for (int j = 0; j < 100001; j++) {
                isprime[j] = true;
            }

            for (int i = 0; i < numprimes; i++) {
                int p = primes[i];
                int start;

                if (p >= M) start = p*2;
                else start = M + ((p - M % p)%p);

                for (int j = start; j <= N; j += p) {
                    isprime[j - M] = false;
                }
            }

            for (int i = M; i <= N; i++) {
                if (isprime[i-M]) System.out.println(i);
            }
        }
    }
}

SPOJ Prime Generator Code in C# (C Hash) Language:

using System;
class PRIME1 {
    static void Main() {

        int[] primes = new int[4000];
        int numprimes = 0;

        primes[numprimes++] = 2;
        for (int i = 3; i <= 32000; i+=2) {
            bool isprime = true;
            double cap = Math.Sqrt(i) + 1.0;
            for (int j = 0; j < numprimes; j++) {
                if (j >= cap) break;
                if (i % primes[j] == 0) {
                    isprime = false;
                    break;
                }
            }
            if (isprime) primes[numprimes++] = i;
        }

        int T,N,M;
        T = int.Parse(Console.ReadLine());

        for (int t = 0; t < T; t++) {
            if (t > 0) Console.WriteLine("");

            string[] parts = Console.ReadLine().Split(' ');
            M = int.Parse(parts[0]);
            N = int.Parse(parts[1]);


            if (M < 2) M = 2;
            double cap = Math.Sqrt(N)+1;

            bool[] isprime = new bool[100001];
            for (int i = 0; i < 100001; i++) isprime[i] = true;

            for (int i = 0; i < numprimes; i++) {
                int p = primes[i];
                if (p >= cap) break;
                int start;

                if (p >= M) start = p*2;
                else start = M + ((p - M % p)%p);

                for (int j = start; j <= N; j+= p) {
                    isprime[j - M] = false;
                }
            }

            for (int i = M; i <= N; i++) {
                if (isprime[i-M] == true) Console.WriteLine(i);
            }
        }
    }
}

SPOJ Prime Generator Code in Ruby Language:

primes = [2]

3.step(32000,2) do |i|
    isprime = true
    cap = Math.sqrt(i) + 1

    primes.each do |p|
        if (p >= cap)
            break
        end

        if (i % p == 0)
            isprime = false
            break
        end
    end

    if isprime
        primes << i
    end
end
numprimes = primes.length

T = gets.to_i


output = ""
t = 0
while t < T
    print "\n" if t > 0
    line = gets.split(" ")
    m = line[0].to_i
    n = line[1].to_i

    m = 2 if m < 2

    cap = Math.sqrt(n) + 1

    notprime = {}

    i = 0
    while i < numprimes
        p = primes[i]
        i+=1
        if (p >= cap)
            break
        end

        if (p >= m)
            start = p*2
        else 
            start = m + ((p - m % p)%p)
        end

        j = start
        while j <= n
            notprime[j] = true
            j += p
        end
    end

    i = m
    while (i <= n)
        if (notprime[i] == nil)
            print i,"\n"
        end
        i+=1
    end
    t += 1
end

SPOJ Prime Generator Code in Python Language:

Hint : More than simple and smaller but great. It's in Python

from math import sqrt
primes = [2]

for i in range(3,32000,2):
    isprime = True

    cap = sqrt(i)+1

    for j in primes:
        if (j >= cap):
            break
        if (i % j == 0):
            isprime = False
            break
    if (isprime):
        primes.append(i)

T = input()
output = ""
for t in range(T):

    if (t > 0):
        output += "\n"

    M,N = raw_input().split(' ')
    M = int(M)
    N = int(N)
    cap = sqrt(N)+1

    if (M < 2):
        M = 2

    isprime = [True]*100001

    for i in primes:
        if (i >= cap):
            break

        if (i >= M):
            start = i*2
        else:
            start = M + ((i - M % i)%i)

        falseblock = [False] * len(isprime[start-M:N+1-M:i]);
        isprime[start-M:N+1-M:i] = falseblock

    for i in range(M,N+1):
        if (isprime[i-M] == True):
            output += str(i) + "\n"

print output[:-1]

Tags: Sphere Online Judge Solutions, SPOJ Prime Generator solution, SPOJ online Judge Solution Prime Generator solution in different language