Thread: Function to return list of all prime numbers in range

My apologies if this is the wrong mailing list.

I've created a function that returns a list of all prime numbers in a range.
eg: SELECT public.all_prime(190, 223);

191,193,197,199,211,223

I'd like to submit this the the contrib lib, but I could not find the correct
email list. Use as you wish.

The code is below.
==================================================================================
CREATE OR REPLACE FUNCTION public.all_prime(INT4, INT4)
RETURNS TEXT AS
-- Returns a list of all prime numbers in the range of $1 to $2
-- Contibuted by Melvin Davidson
-- Computer & Communication Technologies, Inc.
-- mdavidson@cctus.com
$BODY$
DECLARE
  v_start               ALIAS FOR $1;
  v_end         ALIAS FOR $2;
  v_test                INT4;
  v_divisor     INT4;
  v_prime_list  TEXT DEFAULT '';
  v_msg         TEXT;
BEGIN

        v_test = v_start;

        WHILE (v_test <= v_end) LOOP

                v_divisor = 2;
                WHILE (v_divisor <= v_test) LOOP

                        IF mod(v_test, v_divisor) = 0 AND v_divisor < v_test THEN
                                EXIT;
                        ELSE
                                IF mod(v_test, v_divisor) = 0 AND v_divisor = v_test THEN
                                        IF v_prime_list > '' THEN
                                                v_prime_list = v_prime_list ||  ',';
                                        END IF;
                                        v_prime_list = v_prime_list || v_test::text;
                                END IF;
                        END IF;
                        v_divisor = v_divisor +1;

                END LOOP;
                v_test = v_test + 1;

        END LOOP;

        RETURN v_prime_list;
END;
$BODY$
  LANGUAGE 'plpgsql' VOLATILE;

GRANT EXECUTE ON FUNCTION public.all_prime(INT4, INT4) TO public;
COMMENT ON FUNCTION public.all_prime(INT4, INT4) IS 'Returns list of all prime numbers from $1 to $2';
==================================================================================

Hi Melvin,
Here is a slightly optimized version of this function....
It returns the exact same results, just runs about 1000x faster.
I've also marked it as "immutable", that's probably what you wanted,
not Volatile.

select all_prime(10000,11000)
-- Total runtime: 2868.264 ms

select all_prime2(10000,11000);
-- Total runtime: 3.662 ms



CREATE OR REPLACE FUNCTION public.all_prime2(v_start INT4, v_end INT4)
RETURNS TEXT AS $BODY$
DECLARE
  v_test        INT4;
  v_divisor     INT4;
  v_prime_list  TEXT;
BEGIN
  <<OUTER>>
    FOR v_test IN v_start .. v_end LOOP
      IF v_test = 2 THEN
        v_prime_list = '2';
      END IF;

      CONTINUE WHEN mod(v_test,2) = 0;

      FOR v_divisor IN 3 .. ceil(sqrt(v_test)) BY 2 LOOP
        CONTINUE OUTER WHEN mod(v_test,v_divisor) = 0;
      END LOOP;

    IF v_prime_list IS NOT NULL THEN
      v_prime_list = v_prime_list || ',';
    END IF;
    v_prime_list = coalesce(v_prime_list,'') || v_test::text;
  END LOOP OUTER;

  RETURN v_prime_list;
END; $BODY$
LANGUAGE 'plpgsql' IMMUTABLE;





-----Original Message-----
From: pgsql-general-owner@postgresql.org
[mailto:pgsql-general-owner@postgresql.org] On Behalf Of Melvin Davidson
Sent: Monday, February 12, 2007 2:03 PM
To: pgsql-general@postgresql.org
Subject: [GENERAL] Function to return list of all prime numbers in range


My apologies if this is the wrong mailing list.
I've created a function that returns a list of all prime numbers in a
range.
eg: SELECT public.all_prime(190, 223);
191,193,197,199,211,223
I'd like to submit this the the contrib lib, but I could not find the
correct
email list. Use as you wish.
The code is below.
========================================================================
==========
CREATE OR REPLACE FUNCTION public.all_prime(INT4, INT4)
RETURNS TEXT AS
-- Returns a list of all prime numbers in the range of $1 to $2
-- Contibuted by Melvin Davidson
-- Computer & Communication Technologies, Inc.
-- mdavidson@cctus.com
$BODY$
DECLARE
  v_start               ALIAS FOR $1;
  v_end         ALIAS FOR $2;
  v_test                INT4;
  v_divisor     INT4;
  v_prime_list  TEXT DEFAULT '';
  v_msg         TEXT;
BEGIN
        v_test = v_start;
        WHILE (v_test <= v_end) LOOP
                v_divisor = 2;
                WHILE (v_divisor <= v_test) LOOP
                        IF mod(v_test, v_divisor) = 0 AND v_divisor <
v_test THEN
                                EXIT;
                        ELSE
                                IF mod(v_test, v_divisor) = 0 AND
v_divisor = v_test THEN
                                        IF v_prime_list > '' THEN
                                                v_prime_list =
v_prime_list ||  ',';
                                        END IF;
                                        v_prime_list = v_prime_list ||
v_test::text;
                                END IF;
                        END IF;
                        v_divisor = v_divisor +1;
                END LOOP;
                v_test = v_test + 1;
        END LOOP;
        RETURN v_prime_list;
END;
$BODY$
  LANGUAGE 'plpgsql' VOLATILE;
GRANT EXECUTE ON FUNCTION public.all_prime(INT4, INT4) TO public;
COMMENT ON FUNCTION public.all_prime(INT4, INT4) IS 'Returns list of all
prime numbers from $1 to $2';
========================================================================
==========