DZone Snippets: numbers code

A solution for the "Carmichael Numbers" problem

jmftrindade (Joana M. F. da Trindade) — Thu, 24 Apr 2008 23:16:02 GMT

A solution for the "Carmichael Numbers" problem.

Problem description:
http://icpcres.ecs.baylor.edu/onlinejudge/external/100/10006.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.04.24



/* 

 * Solution for "Carmichael Numbers" problem.

 * UVa ID: 10006

 */

#include 

#include 



#define MAXPRIME 65001



using namespace std;



/*

 * Modular exponentiation algorithm. Returns b^e mod m.

 */

unsigned long long fast_mod_pow(unsigned long long b, unsigned long long e, unsigned long long m) {

    unsigned long long r = 1;

    while (e > 0) {

        if ((e & 1) == 1) {

	    r = (r * b) % m;

        }

        e >>= 1;

        b = (b * b) % m;

    }

    return r;

}



/* 

 * Generates all prime numbers up to MAXPRIME. Based on

 * the Sieve of Eratosthenes.

 */

void gen_primes(bool p[]) {

    p[0] = p[1] = false;

	

    /* 

     * starting at number 2 and going to the upper limit, mark 

     * all numbers as potential primes 

     */  

    for (int i=2; i        p[i] = true;

    }

	

    int m = floor(sqrt(MAXPRIME));

    int n;

    /* 

     * mark all multiples of a prime as non-primes. this has to be done for primes 

     * only up to the square root, since every number in the array has at least 

     * one factor smaller than the square root of the limit. 

     */

    for (int i=2; i        if (p[i]) {

       	    n = MAXPRIME / i;

	    for (int j=2; j<=n; j++) {

	        p[i * j] = false;

	    }

	}

    }

}



/* generates all carmichael numbers up to the given limit by performing the fermat test */

void gen_carmi(bool c[], bool p[]) {



    /* initialize carmichael numbers array with false */

    memset(c, 0, MAXPRIME * sizeof(bool));

	

    /* 

     * starting from the first non-prime, mark all 

     * odd numbers as potential carmichael numbers 

     */

    for (int i=9; i	c[i] = true;

    }

	

    /* 

     * again, for all odd numbers, we exclude the primes and perform

     * the fermat test for 2 <= a <= n-1.

     */

    for (int n=9; n	/* VERY IMPORTANT! check first if this number is prime, otherwise we get TLE */

	if (p[n]) {

	    c[n] = false;

	    continue;

	}

	for (int a=2; a<=n-1; a++) {

	    if (fast_mod_pow(a,n,n) != a) {

	        c[n] = false;

		break;

	    } 

	}	

    }

}



/* main */

int main() {

    unsigned long long n; /* number */

    unsigned long long a; /* a of the fermat test */

    bool prime[MAXPRIME]; /* prime numbers array */

    bool carmi[MAXPRIME]; /* carmichael numbers array */

	

    gen_primes(prime);

    gen_carmi(carmi, prime);

	

    while (cin >> n && (n != 0)) {	

        if (carmi[n]) {

            cout << "The number " << n << " is a Carmichael number." << endl;

        } else {

            cout << n << " is normal." << endl;

        }

    }

    return 0;

}

ruby is_numeric? extension to String

sikelianos (Zeke Sikelianos) — Fri, 18 Jan 2008 07:46:24 GMT



class String

  def is_numeric?

    Float self rescue false

  end

end

Euclid's extended algorithm

scvalex (Alexandru Scvortov) — Fri, 22 Jun 2007 14:59:27 GMT

Basically Euclid's algorithm for finding the largest common denominator, this one is modified in order to obtain the numbers d, x, y, where d is the dennominator and they check the following equation:
d = ax + by



def euclidExtended(a, b):

  if b == 0:

    return a, 1, 0

  dd, xx, yy = euclidExtended(b, a % b)

  d, x, y = dd, yy, xx - int(a / b) * yy

  return d, x, y

Perfect Numbers

dpbBryan (Bryan Abrams) — Fri, 24 Nov 2006 22:24:03 GMT

// School project



/*

	Bryan Abrams

	Prof Bioano

	Struct Programming TR at 11

	Homework Five (perfect numbers)

	For Description, see Explain();

*/



#include 

using namespace std;



//-----start prototypes-----//

void Explain();

int GatherUserData(int,int);

int AnalyzeNumber(int);

void PrintResults(int,int,int);

//-----end   prototypes-----//



int main()

{

	int num1, numRet, numRet2;

	char cont = 'Y';



	Explain();



	do {

		cout << "\nPlease, enter an integer: ";

		cin >> num1;



		numRet = AnalyzeNumber(num1);

		numRet2 = GatherUserData(num1,numRet);

		PrintResults(num1,numRet,numRet2);



		cout << "Do you wish to continue? ";

		cin >> cont;

	}while(toupper(cont) == 'Y');



	return 0;

}



void Explain()

{

	cout << "A number is said to be perfect if the sum of its divisors (except for itself)\n"

		 << "is equal to itself. For example 6, is a perfect number because the sum of its\n"

		 << "divisors (1 + 2 + 3) is equal to 6. The number 8 is said to be defiecient\n"

		 << "because the sum of its divisors (1 + 2 + 4) is only 7. The Number 12 is said\n"

		 << "to be abudant because the sum of its divisors (1 + 2 + 3 + 4 + 5 + 6) is 16.\n\n";

	return;

}



int GatherUserData(int num1, int num2)

{

	if(num2 > num1)

		return 3; // abudant

	else if(num2 < num1)

		return 2; // deficient

	else

		return 1; // perfect

}



int AnalyzeNumber(int num)

{

	int numberTot = 0;

	int numberReturn = 0;



	for(int i = 1; i <= num; i++)

	{

		numberTot = num % i;

		if((numberTot == 0) && (i != num))

		{

			numberReturn += i;

		}

	}



	return numberReturn;

}



void PrintResults(int num1, int retNum, int retNum2)

{

	cout << "The sum of the factors of " << num1 << " is " << retNum << endl;

	if(retNum2 == 1)

		cout << num1 << " is a perfect number." << endl;

	else if(retNum2 == 2)

		cout << num1 << " is a deficient number." << endl;

	else if(retNum2 == 3)

		cout << num1 << " is a abundant number." << endl;



	return;

}

Ordinals for All Numeric Types

jswizard (JavaScript Wizard) — Fri, 04 Aug 2006 22:46:04 GMT

This snippet will extend all numerical types with a method for returning the English ordinal, i.e. 1st, 2nd, 3rd, 4th, etc.



class Numeric

  def ordinal

    cardinal = self.to_i.abs

    if (10...20).include?(cardinal) then

      cardinal.to_s << 'th'

    else

      cardinal.to_s << %w{th st nd rd th th th th th th}[cardinal % 10]

    end

  end

end

 

[1, 22, 123, 10, -3.1415].collect { |i| i.ordinal }

=> ["1st", "22nd", "123rd", "10th", "3rd"]

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 2.5 License.

Float to HTML fraction entity

sporkyy (Todd Sayre) — Mon, 24 Jul 2006 21:14:06 GMT

Uses HTML entities to display pretty fractional values for applicable floating point numbers.



class Float

    def html_fraction

        self.to_s.

            sub(/(.+)\.0$/,     '\1'        ).  # Zero decimal

            sub(/(-?\d+)\.25$/, '\1¼').  # One quarter

            sub(/(-?\d+)\.5$/,  '\1½').  # One half

            sub(/(-?\d+)\.75$/, '\1¾').  # Three quarters

            sub(/^(-?)0(&.+)/,  '\1\2'      )   # Strip leading zeroes

    end

end

And it works something like this:



>> (0.1).html_fraction

=> 0.1

>> (0.25).html_fraction

=> ¼

>> (0.50).html_fraction

=> ½

>> (0.75).html_fraction

=> ¾

>> (1.0).html_fraction

=> 1.0

>> (2.25).html_fraction

=> 2¼

>> (3.5).html_fraction

=> 3½

>> (4.75).html_fraction

=> 4¾

>> (5.85).html_fraction

=> 5.85

>> (-1.5).html_fraction

=> -1½

>> (-1.6).html_fraction

=> -1.6;

>> (-0.25).html_fraction

=> -¼

IsReallyInteger

austegard (Oskar Austegard) — Thu, 19 Jan 2006 02:50:56 GMT



----------------------------------------------------------------------------

--Purpose: Checks that the input string is really an integer of the specified type.  

-- To be used in place of the ISNUMERIC function, as it can't be trusted.

-- See http://www.sql-server-performance.com/forum/topic.asp?TOPIC_ID=10194

--Inspired by: http://www.aspfaq.com/show.asp?id=2390 

--Created: 10/20/05 by Oskar Austegard.

--Updated: 11/16/05 by Oskar Austegard - fixed bugs

----------------------------------------------------------------------------

ALTER FUNCTION dbo.IsReallyInteger

(  

  @Num varchar(64), --Input string to be checked

  @Type varchar(8) --Type of integer: bigint, int, smallint, tinyint

)  

RETURNS BIT  

BEGIN  

  --Get the absolute value of the number by removing a leading - or +

  DECLARE @AbsNum varchar(64), @Length tinyint

  SET @AbsNum = CASE WHEN LEFT(@Num, 1) IN ('-', '+') THEN SUBSTRING(@Num, 2, LEN(@Num)) ELSE @Num END



  --Remove leading zeros

  WHILE LEN(@AbsNum) > 1 AND LEFT(@AbsNum, 1) = '0'

    SET @AbsNum = SUBSTRING(@AbsNum, 2, LEN(@AbsNum))



  SET @Length = LEN(@AbsNum)  

  --Reinsert the - in negative numbers

  SET @Num = CASE WHEN LEFT(@Num, 1) = '-' THEN '-' + @AbsNum ELSE @AbsNum END



  --Check for empty string or non-digits

  IF @AbsNum = '' OR PATINDEX('%[^0-9]%', @AbsNum) > 0

    RETURN 0



  --Check limits by type

  IF (@Type = 'bigint' AND (@Length < 19 OR (@Length = 19 AND (@AbsNum < '9223372036854775807' OR @Num = '-9223372036854775808'))))

    OR (@Type = 'int' AND (@Length < 10 OR (@Length = 10 AND (@AbsNum < '2147483648' OR @Num = '-2147483648'))))

    OR (@Type = 'smallint' AND (@Length < 5 OR (@Length = 5 AND (@AbsNum < '32768' OR @Num = '-32768'))))

    OR (@Type = 'tinyint' AND LEFT(@Num, 1) <> '-' AND (@Length < 3 OR (@Length = 3 AND @AbsNum < '256')))

    RETURN 1 --Success

  --Else

  RETURN 0 --Failure

END

Oskar Austegard
http://mo.notono.us

Create a Number Table

austegard (Oskar Austegard) — Thu, 19 Jan 2006 02:47:15 GMT

Created 08/26/05 by Oskar Austegard (http://mo.notono.us) from article at
http://msdn.microsoft.com/library/en-us/dnsqlpro03/html/sp03k1.asp
Can be used inline in functions, or to create a standalone Numbers table (as required by dbo.Split).



--Creates a table of sequential numbers, useful for all sorts of things

--Created 08/26/05 by Oskar Austegard from article at 

--http://msdn.microsoft.com/library/en-us/dnsqlpro03/html/sp03k1.asp

--Limits: @Min and @Max must be between -2147483647 and 2147483647, including.

--If @Max <= @Min, only a single record with @Min is created

ALTER FUNCTION dbo.NumberTable (@Min int, @Max int)

RETURNS @T TABLE (Number int NOT NULL PRIMARY KEY)

AS

BEGIN

  -- Seed the table with the min value

  INSERT @T VALUES (@Min)

  --Loop until all the rows are created, inserting ever more records for each iteration (1, 2, 4, etc)

  WHILE @@ROWCOUNT > 0

	BEGIN

	  INSERT @T 

	  --Get the next values by adding the current max - start value + 1 to each existing number

	  --need to calculate increment value first to avoid arithmetic overflow near limits of int

	  SELECT t.Number + (x.MaxNumber - @Min + 1)

	  FROM @T t

	    CROSS JOIN (SELECT MaxNumber = MAX(Number) FROM @T) x --Current max

	  WHERE

	    --Do not exceed the Max - shift the increment to the right side to take advantage of index

	    t.Number <= @Max - (x.MaxNumber - @Min + 1)

	END

  RETURN

END

number-lines function

gregg.irwin (Gregg Irwin) — Tue, 10 Jan 2006 06:01:23 GMT



    number-lines: func [

        "Insert leading line numbers for each line."

        input [string! block!]

        /local lines lead-wd

    ][

        lines: any [all [block? input  input] parse/all input form newline]

        lead-wd: length? form length? lines

        repeat i length? lines [

            insert lines/:i join pad-num i lead-wd ": "

        ]

        either block? input [lines] [rejoin delimit lines newline]

    ]

Defining a custom validates in rails

zzzrByte (Tal Ater) — Wed, 19 Oct 2005 21:47:46 GMT

in the model:



class User < ActiveRecord::Base

  require 'validations'



  validates_positive_or_zero :number

  

end

in /lib/validations.rb:



def validates_positive_or_zero(*attr_names)

  configuration = { :message => "Cannot be negative" }

  configuration.update(attr_names.pop) if attr_names.last.is_a?(Hash)

  validates_each attr_names do |m, a, v| m.errors.add(a, configuration[:message]) if v<0 end

end