Zero Wind – Jamie Wong Inside the mind of a Waterloo Software Engineering student

12Nov/094

SPOJ Problem 2: Prime Generator (PRIME1)

Problem: Prime Generator

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

Concept The idea behind every solution here (with some variation) is to generate all the prime numbers that could be factors of numbers up to the maximum endpoint 1 billion. That square root happens to be around 32000. Using this array, do a bounded Sieve of Eratosthenes only in the range requested. In languages like php and python, it turns out that it's more efficient to build an associative array and check if the index is set than it is to generate a huge boolean array.

Code

C++

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

/// PRIME1 - C++ (g++)
// AC Time: 2.52s
// NOTE: I am aware that the use of vector and set actually
//  makes this code run _slower_
// I used vector and set simply as a way of practicing STL
#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><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;
}

Tagged as: , , , , , , , , , , 4 Comments
8Nov/090

SPOJ Problem 1

When I saw that Thor had done solutions to the first few problems of Project Euler in many many languages, I thought "Hey! That's a good idea!" but didn't want to copy exactly.

So instead I'm doing solutions to some problems on SPOJ. SPOJ is an online judge system full of algorithmic problems. This is one of the things that Hanson Wang did to get as good as he is. The solutions I'll be providing here are going to be very simple problems, so don't expect any magic. The beautiful thing about SPOJ is the sheer number of languages it will judge. I figured this was the perfect playground to make sure my code worked in all the languages I try.

Problem: Life, the Universe, and Everything

Your program is to use the brute-force approach in order to find the Answer to Life, the Universe, and Everything. More precisely... rewrite small numbers from input to output. Stop processing input after reading in the number 42. All numbers at input are integers of one or two digits.

Solutions - In order of frequency that I use the language

C++

1
2
3
4
5
6
7
8
9
10
11
12
13

//TEST AC - CPP (g++)
#include <iostream>
using namespace std;
 
int main() {
	int n;
	while(1) {
		cin >> n;
		if (n == 42) break;
		cout << n << endl;
	}
	return 0;
}

C99

1
2
3
4
5
6
7
8
9
10
11

//TEST AC - (gcc C99)
#include <stdio.h>
int main() {
	int n;
	while(1) {
		scanf("%d",&n);
		if (n == 42) break;
		printf("%d\n",n);
	}
	return 0;
}

php

1
2
3
4
5
6
7
8

<?
//TEST AC - PHP
while(1) {
	fscanf(STDIN,"%d",$n);
	if ($n == 42) break;
	print "$n\n";
}
?>

Python

1
2
3
4
5
6

#TEST AC - Python
while 1:
	num = input()
	if (num == 42):
		break
	print num

Bash

1
2
3
4
5
6
7
8
9
10

#!/bin/bash
# TEST AC - BASH
 
while true; do
	read n
	if [ $n -eq 42 ]; then
		break
	fi
	echo "$n"
done

Ruby

1
2
3
4
5
6
7
8

#TEST AC - Ruby
while 1
	n = gets.to_i
	if n == 42
		break
	end
	puts n
end

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

//TEST AC - Java
import java.io.*;
import java.util.*;
 
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
 
		while(true) {
			int n = in.nextInt();
			if (n == 42) break;
			System.out.println(n);
		}
	}
}

Perl

1
2
3
4
5
6
7
8
9

#TEST AC - Perl
while (1)
{
	$n = <STDIN>;
	if ($n == 42) {
		last;
	}
	print $n
}

C#

1
2
3
4
5
6
7
8
9
10
11
12

//TEST AC - C# (gmcs + Mono)
using System;
class WelcomeCSS {
	static void Main() {
		while(true) {
			int n;
			n = int.Parse(Console.ReadLine());
			if (n == 42) break;
			Console.WriteLine(n);
		}
	}
}

GNU Pascal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

{TEST AC - GPC Pascal}
 
program TEST;
 
var n:integer;
 
begin
	while true do
		begin
			readln(n);
			if n = 42 then begin
				break;
			end;
			writeln(n);
		end;
end.

You can see Thor's Project Euler solutions here: Derek Thurn's Website - Project Euler

Tagged as: , , , , , , , , , , No Comments
   

Categories

Pages

Links