#include <coding challange>

[Yourmysin]

This is a coding challange based off an idea i was thinking about!

You have to code a program that when 2 numbers are entered, it will calculate all prime numbers between those two numbers. This has to work for Any numbers between -10000 to 10000.

Feel free to code with the most natural language to you!

The first few people to code a working program will be reconized on yourmysin.info, as well as all other entrys.

I myself will be participating in this coding challange using both c# and c++.

[PoyBoy]

Primes...

/smiles. I like primes

[jool]

<form action="<?php echo $_SERVER['PHP_SELF'];?>" method="post">

<input type="text" name="num1"/>

<input type="text" name="num2"/>

<input type="submit"/>

</form>



<?php

$num1 = isset($_POST['num1']) && is_numeric($_POST['num1']) ? intval($_POST['num1']) : -1;

$num2 = isset($_POST['num2']) && is_numeric($_POST['num2']) ? intval($_POST['num2']) : -1;



if($num1 < 0 || $num2 < 0) exit();



if($num1 > $num2){

    $tmp = $num1;

    $num1 = $num2;

    $num2 = $tmp;

}



for($i = $num1; $i < $num2; $i++){

    $is_prime = $i > 1;

    for($j = 2; $j <= sqrt($i); $j++){

        if($i % $j == 0){

            $is_prime = false;

            break;

        }

    }

    if($is_prime){

        echo "$i<br/>";

    }

}

?>

PHP ftw! :)

[Yourmysin]

Will somebody confirm jool?

I cant test php :P

[Mick]

Mines in pure C.

This will be simple so people can get a good look, but beware I am away from my compiler atm so there may be errors.

//Prime Number Program By Mick

#include <stdio.h>

#include <math.h>

int isprime(int num){int i;

for (i=num-1;i>1;i--){if (num==floor(num/i)*i) {return false;}}

return true;}

int main(){

int n1,n2,n3;

printf("Enter Number 1 ");scanf("%d",n1);

printf("Enter Number 2 ");scanf("%d",n2);

if (n1<0){n1=0;}if (n2<0){n2=0;}

if (n1>n2){n3=n2;n2=n1;n1=n3;}

for(n3=n1;n3<n2;n3++){if (isprime(n3)) {printf("%dn",n3);}}

return 0;

}

EDIT: Ported to javascript :)

(TESTED) EDIT: Optimised A Little :)

//Prime Number Script By Mick 

function isprime(num){

if (!(num%2)){return false;}

if (!(num%5)){return false;}

if (!(num%9)){return false;}

var sn=Math.sqrt(num);

for (i=(num-1)/2;i>sn;i--){if (num==Math.floor(num/i)*i) {return false;}} 

return true;} 

var n1,n2,n3;

n1=prompt("Enter Number 1",""); 

n2=prompt("Enter Number 2",""); 

if (n1<0){n1=0;}if (n2<0){n2=0;} 

if (n1>n2){n3=n2;n2=n1;n1=n3;} 

for(n3=n1;n3<n2;n3++){if (isprime(n3)) {document.write("<div />"+n3);}}

Still more to come!

[stingwray]

Haskell

primeBetween :: Int-> Int -> [Int]

-- Outputs all the prime numbers between the two inputs. --

-- Pre: int > 0 --

primeBetween int1 int2

    |    int1 == int2 = [ x | x <- [int1], isPrime x ]

    |    int1 < int2 = [ x | x <- [int1..int2], isPrime x ]

    |    int2 < int1 = [ x | x <- [int2..int1], isPrime x ]



isPrime :: Int -> Bool

-- Outputs True if Input is Prime, False Otherwise. --

-- Pre: int > 1 --

isPrime int

    |    int < 2 = False

    |    otherwise = findPrime 2

        where

            findPrime :: Int -> Bool

            findPrime n

                | fromIntegral n > sqrt (fromIntegral int) = True

                | int `mod` n == 0 = False

                | otherwise = findPrime (n + 1)

[Rab]

this is way too easy?

[cooper]

No, I think people are simply choosing to omit this particular bit of the requirement:

This has to work for any possible numbers.

Try putting in some insanely high value. Preferably one that can't be represented with 64 bits (though more than 31 bits should kill most of these programs already).

Javascript tops at 63 bits (64-bit signed).

This C example at 31 bits (32-bit int, signed). Change the ints to unsigned long long and you've got 64, but that's still not "any possible number".

Haskell's Int implementation can vary, but is only guaranteed to work everywhere with numbers topping off at 2^29 - 1

PHP's integer type is a 32-bit signed value, so again, limited.

[jool]

Yep, intentionally omitted. But if you're going to do math on that scale you need specialized libraries and smarter math.

Javas BigInteger is practical if you're doing it for real since it is of arbitrary precision. It can also generate large (probable) primes and determine if numbers are likely to be prime relatively quickly with built in functionality.

edit:

Found out that php also has a library for huuuge numbers so I rewrote it to use that, it even does negative numbers now. So I think it qualifies for the "any number" requirement now.

<form action="<?php echo $_SERVER['PHP_SELF'];?>" method="post">

<input type="text" name="num1"/>

<input type="text" name="num2"/>

<input type="submit"/>

</form>



<?php

ini_set("max_execution_time","0");



$num1 = isset($_POST['num1']) ? gmp_init($_POST['num1']) : false;

$num2 = isset($_POST['num2']) ? gmp_init($_POST['num2']) : false;



if(!$num1 || !$num2) exit();



if(gmp_cmp($num1,$num2) > 0){

    $tmp = $num1;

    $num1 = $num2;

    $num2 = $tmp;

}



for($i = $num1; gmp_cmp($i,$num2) < 0; $i = gmp_add($i,1)){

    $is_prime = gmp_cmp($i,1) > 0 || gmp_cmp($i,-1) < 0;

    $i_sqrt = gmp_sqrt(gmp_abs($i));

    for($j = gmp_init(2); gmp_cmp($j,$i_sqrt) <= 0; $j = gmp_add($j,1)){

        if(gmp_cmp(gmp_div_r($i,$j),0) == 0){

            $is_prime = false;

            break;

        }

    }

    if($is_prime){

        echo gmp_strval($i)."<br/>";

    }

}

?>

I didn't use the gmp_prob_prime since that would be cheating :)

[Mick]

Well, first of all, my C code is more of an example then an implementation.

There are many faster ways to find primes.

And on a technicallity he said any possible number, he didnt specify possible as in with any number, or possible as in using the language's built in functions :), but im not that much of a cheater.

My next example will be in C++ and I just might have to whip out my infinite number class.

[spektormax]

well thers a theroretical limit becasue of the amount of memoery you have to make a GIANT number and it woudl be phisicly impossible to calulate a primes up to leik a 5000 digit numebr in any reasonable amount of time, I have a c++ implintation of direct search but you cant just say any possiblem, that implies decimals and negatives, and non real numebrs so the asnwer is its impossilbe. if you said possitive integers and gave a limit then yes we could code it

[FrihD]

I think you can't test if a number is a prime without testing each number below its square root. no ? so what's the point in finding the primes in a range ?

A not too bad way to find them is the "crible d'ératostène" (i don't remember the english name). I once have to code it in Maple language.

[cooper]

well thers a theroretical limit becasue of the amount of memoery you have to make a GIANT number and it woudl be phisicly impossible to calulate a primes up to leik a 5000 digit numebr in any reasonable amount of time

See, now that bit he didn't specify. The only requirement is that the code of your sulotion can deal with it.

If the machine lacks the memory for the program, you can still get a bigger machine. The main thing appears to be that the program itself shouldn't have to change.

[addisonzinser]

cooper do you work for google? lol

[cooper]

No, unfortunately not. I work for some company that doesn't do a lot with elec *cough* *cough* Gee! tronics.

Yeah, that probably works better visually than in plain text...

[spektormax]

technicly ther a prime testing algarithusm, that dont need everynumber bellow google it I was thinking of them when I was fullign around with crackign RSA on a large scale

[stingwray]

I'll add another recusion function to my Haskell program which will break the numbers down then. Not that hard as i have done it for Modular Power functions when discovering Carmichael numbers.

[Yourmysin]

I said any possible numbers but i really ment any possible numbers withen reason.

So, i will change it to "work with any possible numbers between -10000 to 10000

[deathwarder]

hmmm, I made a very efficient program in c++ that did just this, and was modular enough to work beyond 64bit numbers.

[RompeRatones]

Some python here

#!/usr/bin/env python

# -*- coding: UTF-8 -*-



while True:

    try:

        number1= int(raw_input('input number1: '))

        if number1>10000 or number1< (-10000):

            print "number not between values 10000 -10000"

            raise ValueError

        break

    except ValueError:

        print "Not valid.  Try again..."



while True:

    try:

        number2= int(raw_input('input number2: '))

        if number2>10000 or number2< (-10000):

            print "number not between values 10000 -10000"

            raise ValueError

        if number2==number1:

            print "both numbers are the same... choose another"

            raise ValueError

        break

    except ValueError:

        print "Not valid.  Try again..."

        

def showMe(number):

        

        for foo in range(2, number):

            if  number%foo==0:

                return False

            

        return True

        



    

def ShowPrimes(min, max):

        for numero_primo in range(min,max+1):

            res=showMe(abs(numero_primo))

            if res:

                if numero_primo !=0: #  division by 0 doesnt count

                    print numero_primo

        

        

VectorControl=[number1,number2]

numMin=min(VectorControl)

numMax=max(VectorControl)

ShowPrimes(numMin,numMax)