/* 
 * Solution for "Carmichael Numbers" problem.
 * UVa ID: 10006
 */
#include <iostream>
#include <math.h>

#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<MAXPRIME; 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<m; 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<MAXPRIME; i+=2) {
	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<MAXPRIME; n+=2) {
	/* 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;
}

class String
  def is_numeric?
    Float self rescue false
  end
end

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

/*
	Bryan Abrams
	Prof Bioano
	Struct Programming TR at 11
	Homework Five (perfect numbers)
	For Description, see Explain();
*/

#include <iostream>
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;
}

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"]

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

>> (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
=> -¼

----------------------------------------------------------------------------
--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  

--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: 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]
    ]

class User < ActiveRecord::Base
  require 'validations'

  validates_positive_or_zero :number
  
end

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