text:
Return each number from a group of numbers
The challenge
The program must return all numbers included into a group (comma and hyphen separated sequence) of numbers.
Rules

s is the sequence string;
all numbers included in s are positive;
numbers will always increase;
numbers will never repeat
when you answer, show the output for s="1,3-5,9,16,18-23"

Examples
input(s)    outputs
-----------------
1           1
1,2         1,2
1-4         1,2,3,4
1-4,6       1,2,3,4,6
1-4,8-11    1,2,3,4,8,9,10,11

Good luck. =)

Will we ever have input sequences that are not constantly increasing, for example: 4-9,1-2 or 1-3,9-6?

Or overlapping? Does the output have to be sorted and not contain duplicates?

@Gareth Yes, this is a code-golf, then please vote-up for the shortest answer. Matt and Peter, I edited the question, please check it. Thanks!

Does it have to be a full program, and is there a restriction on the format of the output?

duplicate?

GolfScript (24 chars)
','/{~.,!{~)),>~}*}%','*

E.g.
$ golfscript.rb expand.gs <<<"1,3-5,9,16,18-23"
1,3,4,5,9,16,18,19,20,21,22,23

I actually have four 24-char solutions, but I chose this one because it doesn't have any alphanumeric characters.
How it works
# On the stack: a string such as "1,3-5,9,16,18-23"
','/
# Split on commas to get ["1" "3-5" "9" "16" "18-23"]
{
    # This is executed for each of those strings in a map
    # So stack holds e.g. "1" or "3-5"

    # Evaluate the string.
    # If it's a single number, this puts the number on the stack.
    # Otherwise it's parsed as a positive number followed by a negative number.
    ~
    # Stack holds e.g. 1 or 3 -5
    # Duplicate the last element on the stack and make a list of that length.
    # If it's negative or zero, the list will be empty
    .,
    # Negate. An empty list => 1; a non-empty list => 0
    !
    # If the string was a single number "n", the stack now holds n 0
    # If the string was a range "m-n", the stack now holds m -n 1
    # The following block will be executed 0 times for "n" and once for "m-n"
    {
        # Here we rely on twos-complement numbers satisfying ~n = -n -1
        # Stack: m -n
        ~))
        # Stack: m -(-n)-1+2  =  m n+1
        ,
        # Stack: m [0 1 2 ... n]
        >
        # Stack: [m m+1 ... n]
        ~
        # Stack: m m+1 ... n
    }*
}%
# On the stack: e.g. [1 3 4 5 9 16 18 19 20 21 22 23]
','*
# Joined by , to give the desired output

How can you expand 3-5 into 3,4,5 without using a single the character -?

@BernaMariano, sorry, I somehow missed your question. I'll expand the answer with a detailed explanation.

Perl 25 26 25
$_ is the sequence string
s/-/../g;$_=join",",eval

Sample session:
[~/] $ perl -M5.010 -pe 's/-/../g;$_=join",",eval' <<< "1,3-5,9,16,18-23"
1,3,4,5,9,16,18,19,20,21,22,23

Added 1 character to the character count for the -n-p option (thanks Gareth, ..kinda).

I've probably done the character counting wrong (with the command line options). Feel free to correct my counting, please

Going by the answer to this question on meta, you only need to add 1 character for the n option.

Remove -M5.010 and exchange -e for -E

golfscript, 46 45
My first ever golf script program, took hours to complete.
{','/{'-'/{~}%.,1-{))+{,}/\-~}{~}if}%","*}:r;

# call:
"1,3-5,9,16,18-23"r

# return:
1,3,4,5,9,16,18,19,20,21,22,23

You can try it at http://golfscript.apphb.com/
My best throw at explaining this atrocity:
{...}:r;     # makes a function block ... and names it r

','/         # slices the top element of stack from each ','
             # so we get ["1" "3-5" "9" "16" "18-23"]

{...}%       # makes a function block ... and calls it for
             # each element in the list

'-'/{~}%     # slices the list by '-' and evals each element
             # from string to int. ["1"] becomes [1],
             # ["3-5"] becomes [3 5]

.,1-         # adds the length of the list -1 on top of the stack
             # so for [1] the stack becomes [1] 0, for [3 5]
             # it becomes [3 5] 1

# next we add two function blocks, they, like the 0/1 just before
# are used by an if clause a tiny bit later. First block is for
# lists that have a 1 on top of them, the latter for ones with 0.

# First block, we have something like [3 5]

))+          # pops the top element of the array, increments
             # it and puts back. [3 6]

## It seems {...}%~ is same as {...}/
## this is why these two are not in the code any more

{,}%         # , makes a list from 0 to n-1, where n is the parameter
             # so we get [[0 1 2] [0 1 2 3 4 5]]

~            # Dumps the outer array, [0 1 2] [0 1 2 3 4 5]

\            # swaps the two arrays

-            # set complement [3 4 5]

~            # dumps the array, so the elements are left in the stack

# Second block, we have something like [16]

~            # just dumps the array, 16

# Blocks end

if           # takes the top three elements of the stack, evaluates the
             # first (0 or 1), runs second if true (anything but
             # [], "", 0 or {} ), otherwise the third.

","*         # joins an array with ","

edit 1: changed the last {}%~ to {}/, also my description was likely wrong.

+1, because anyone doing a program in GolfScript has earned it.

@Gareth Thanks. I first thought I'd just do it the perl way: change - to .. and evaluate it. Then I couldn't find any sane way to build any arrays so I did this. I'm sure someone will come around with a ~20 char solution with golfscript.

I have 24 at the moment, so I'll take 20 as a challenge ;) You can save a few quite easily, though. The problem asks for a program, not a function, so you can lose the initial { and the final }:r; and you can also save one by replacing 1- with (. (Incidentally, IIRC that's one trick I also missed in my first GolfScript program)

PS There is a subtle difference between {...}%~ and {...}/. If you're accessing something further down the stack using integer $ then the first one is simpler, because you don't have to adjust the integer each time to compensate for whatever you're leaving on the stack.

R, 44 bytes
`-`=seq;eval(parse(t=c("c(",scan(,""),")")))

Try it online!
Redefine - to mean seq (i.e. :), surround the input with c() and evaluate the corresponding expression.

K, 47
","/:,/${x+!1+y-x}.'2#'a,'a:"I"$'"-"\:'","\:0:0

Test case
k)","/:,/${x+!1+y-x}.'2#'a,'a:"I"$'"-"\:'","\:0:0
1,3-5,9,16,18-23
"1,3,4,5,9,16,18,19,20,21,22,23"

","/:$,/{{x+!1+y-x}. 2#"J"$"-"\:x}'","\:0:0 for 43 bytes

Jelly, 9 bytes
⁾-ryṣ”,VF

Try it online!
   y         Replace
⁾-r          hyphens with the letter r,
    ṣ”,      split on commas,
       V     evaluate every element,
        F    and flatten.

The range dyad r takes two arguments on either side of it and produces an inclusive range between them.

J, 53 43 41 39 38 characters
;(}.[:i.1+])/&.>".'- ,;'charsub 1!:1[1

Takes input from the keyboard:
   ;(}.[:i.1+])/&.>".'- ,;'charsub 1!:1[1
1-4,8-11
1 2 3 4 8 9 10 11

Output for the requested test case:
   ;(}.[:i.1+])/&.>".'- ,;'charsub 1!:1[1
1,3-5,9,16,18-23
1 3 4 5 9 16 18 19 20 21 22 23

Hassium, 173 Bytes
This was pretty long and might not be competing since there is a trailing , at the end.
 func main(){p="1,2,3,5-8".split(",")for(c=0;c<p.length;c++){e=p[c]if(e.contains("-")){p=e.split("-")for(x=p[0].toInt();x<=p[1].toInt()print(x++ +",")){}}else print(e+",")}}

Run online and see expanded here

Perl (37)
$_=<>;s/^/say join',',/;s/-/../g;eval

when you answer, show the output for s="1,3-5,9,16,18-23", thanks

How about say join",",eval<>=~s/-/../gr at 29 bytes

PowerShell, 79 71 bytes
('('+($args[0]-replace'-','..'-replace',','),(')+')'|iex|%{$_})-join','

Try it online!
The inner part changes "1,5-9,12" into a "(1),(5..9),(12)" format that PowerShell understands, then executes that with iex, which creates an array of arrays. Then iterate through each inner array, then finally join all outer array elements together
Borrows code from my "Help Me Manage My Time" answer
Usage
PS C:\Tools\Scripts\golfing> .\return-each-number-from-a-group-of-numbers.ps1 '1,3-5,9,16,18-23'
1,3,4,5,9,16,18,19,20,21,22,23

-8 bytes thanks to Veskah

You're doing redundant joins, 71 bytes

Perl 6, 36 bytes
$_=get;say join ',',EVAL S:g/\-/../

1,3,4,5,9,16,18,19,20,21,22,23

Python 2.7, 147 138 Bytes

z,f=input().split(','),[]
for i in z:
 x=i.split('-')
 if len(x)>1:f+=range(int(x[0]),int(x[1])+1)
 else:f+=[int(x[0])]
print str(f)[1:-1]

Usage:

>>>python nums.py
"1,3-5,9,16,18-23"
1, 3, 4, 5, 9, 16, 18, 19, 20, 21, 22, 23

Not the best program...

Welcome to PPCG. I think you can make your answer shorter by using 1 space for indents.

Thanks @intrepidcoder, I didn't know that you could use single space indents.

MATLAB, 47 bytes
disp(eval(['[',strrep(input(''),'-',':'),']']))

This snippet reads a string input from the command window, replaces '-' by ':', adds square brackets to the string and then evaluates it, so that the input will be expanded to a full array of numbers.
Example input:
'1,3-5,9,16,18-23'

Example output:
1     3     4     5     9    16    18    19    20    21    22    23

I believe this output is allowed, as the challenge only say that all numbers in a group should be displayed.

comma-separated output would be nicer, though i can se a 5-spaces-separated pattern, thats cool for me :)

K (oK), 40 31 bytes
Solution
,/{{x+!1+y-x}. 2#.:'"-"\x}'","\

Try it online!
Explanation:
Managed more golfing whilst adding the explanation...
,/{{x+!1+y-x}. 2#.:'"-"\x}'","\ / the solution
                           ","\ / split input on ","
  {                      }'     / apply lambda to each
                    "-"\x       / split x on "-"
                 .:'            / value (.:) each (')
               2#               / 2 take (dupe if only 1 element)
   {        }.                  / diadic lambda, 2 args x and y
         y-x                    / y subtract x
       1+                       / add 1
      !                         / range 0..n
    x+                          / add x
,/                              / flatten

Husk, 11 bytes
ṁȯ…mix'-x',

Try it online!

Clojure, 110 bytes
#(clojure.string/join","(for[s(.split %",")[a b][(map read-string(.split s"-"))]r(if b(range a(inc b))[a])]r))

Dealing with strings isn't much fun :(

Python 2, 112 bytes
Pretty simple and straightforward answer.
L=[]
for s in input().split(','):
 if'-'in s:a,b=map(int,s.split('-'));L+=range(a,b+1)
 else:L+=[int(s)]
print L

Try it online!

Ruby -p, 33 bytes
gsub(/(\d+)-(\d+)/){[*$1..$2]*?,}

Try it online!

Japt, 12 bytes
q, c@OvXr-'ò

Try it

Can you replace c@ with £?

@Oliver, as it's an old challenge that doesn't specify its I/O format, I erred on the side of caution, taking input as a comma delimited string and outputting as a flattened array. Normally, though, yes, I'd have specified input as an array of strings, output as a multi-dimensional array and just used £ in place of the first 5 bytes.

Python 2, 90 bytes
lambda s:sum((range(u[0],u[-1]+1)for u in[map(int,t.split('-'))for t in s.split(',')]),[])

Try it online!

Lua (126 bytes)
Just for fun:
(("1,3-5,9,16,18-23"):gsub("(%d+)-(%d+)",function(a,b)t={}for i=a,b do t[#t+1]=math.ceil(i)end return table.concat(t,",")end))


text:
m3ph1st0s's programming puzzle 4 (C/C++): “3-way swap”
My last puzzle has generated some confusion and controversy so I decided to give up, for now, on those "replace one character"-type puzzles.
Hope this 4th puzzle will redeem myself after all the edits in puzzle 3 and will put your brains at work once more.
I've really put up all the effort to make this one as clear as possible and hope you will enjoy it!
So here it goes:
We start from a very short C program:
int main() {
   int a = 93;
   int b = 11;
   int c = 22528;

   // insert your code here

}

Your job will be to swap the values of the variables a,b,c like this: a <= b, b <= c, c <= a. To make it even more clear: new a = old b, new b = old c, new c = old a.
You are required to do this by inserting one single instruction in the line indicated by the comment in the code. To be clear once again, this line will contain only one semicolon (;) indicating the end of the lone instruction. After the execution of this program, a will contain 11, b will contain 22528, c will contain 93.
However, there are some conditions that need to be met. So we'll have 4 different puzzles with different cryteria.
4.1. Do it by using whatever you want. Just one statement. -> most creative solution wins this one.
4.2. Do it without using any comma (,). -> most creative wins
4.3. Do it without any comma and with no more than 4 letters (+any other characters). -> shortest code wins
4.4. Do it without any comma and with no more than 4 letters and no more than 4 digits (+any other characters). -> shortest code wins
To make sure you understood, here's some code that is valid under the condition required but does not solve the problem:
4.1:
I_hereby_call_my_beautiful_function(nice_argument), int q=w, who_the_hell_is(w)+1;

4.2:
one = single + assignment;

4.3:
int w=12345678;

4.4:
int w=1234;

P.S. In case you haven't already noticed, 4.4 is the tough one here (I hope :D).

4.4 21 19 characters
Edit: Now meets all the criteria for 4.4.
c=(b<<=a>>=3)>>8|5;

For 4.4 (14 characters, 1 digit and 4 letters):
int main()
{
  int a = 93;
  int b = 11;
  int c = 22528;

  b<<=a=(c=a)/8;
}

VS2010 with /Wall didn't show any warnings, but I'm still a bit suspicious about using a twice in there (even though it's only modified once).

Classic inplace exchange (20 chars without spaces, category 4.1, 4.2):
c ^= b ^= c ^= b ^= a ^= b ^= a;

Total exist 9 xor-chains that implement this 3-way exchange
c ^= b ^= c ^= b ^= a ^= b ^= a;
c ^= a ^= c ^= b ^= c ^= b ^= a;
c ^= b ^= a ^= b ^= a ^= c ^= a;
a ^= c ^= b ^= c ^= b ^= a ^= b;
a ^= b ^= a ^= c ^= a ^= c ^= b;
a ^= c ^= a ^= c ^= b ^= c ^= b;
b ^= c ^= b ^= a ^= b ^= a ^= c;
b ^= a ^= b ^= a ^= c ^= a ^= c;
b ^= a ^= c ^= a ^= c ^= b ^= c;

and to continue of Gareth idea (No commas, 3 letters, 4 digits)
c=(b<<=a>>=3)/242;

wrong order, but if properly edited and placed in the right category would be real nice

I think you can save 1 character by changing a>>=3 to a/=8

You can do it without semicolons either with the classic if(c=(b<<=a>>=3)/242){} but its a few extra characters.  Also it doesn't meet the 4 letter requirement.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Print integers in any base up to 36

Possible Duplicate:
Integer to string with given radix

This question is inspired by Pythons builtin int function. int is used to convert other numbers or strings into integers. If you are converting a string you can provide the additional parameter base, that contains the base that your number is represented in within the string:
>>> int('137')
137
>>> int('137',base=8)
95
>>> int('ff',base=16)
255
>>> int('1AZ',base=36)
1691

Unfortunately Python doesn't provide a function for the reverse case, where you want to convert a number into a string in a specific base.
Your task is to write such a function.

the function may return the value or print it
you must provide support for all bases between 2 and 36
digits to use are 0123456789abcdefghijklmnopqrstuvwxyz
all languages are allowed
built in functions for this purpose are boring and thus forbidden
shortest code wins

"built in functions for this purpose are boring" - and the problem itself isn't?

huh. i didnt think it was such a bad question :(

I thought it's a bit boring but it's a good exercise for golf beginners... +1 to even out that unfair -1!

In fact, it's a trivial variant on some existing questions, most notably http://codegolf.stackexchange.com/questions/536/integer-to-string-with-given-radix,

APL (25)
{(⎕D,⎕A)[1+⍵⊤⍨⍺⍴⍨⌈⍺⍟⍵+1]}

The left argument is the base, and the right argument is the number.
i.e.
    16{(⎕D,⎕A)[1+⍵⊤⍨⍺⍴⍨⌈⍺⍟⍵+1]}1234
4D2

Befunge, 17x4 = 68 characters
1-&00p&>:!#v_:00v
v-10<  ^/g00\%g <
< >:^@_.# #$v#:!`
"_^#`9::$  <<,+"W

Online interpreter: http://www.bedroomlan.org/tools/befunge-93-playground
First input is base, second is number.
Similar to other solutions here this does not output anything when the number is 0.  I may look at fixing this at some point.

C, 68
c(n,b,r){char*p=1+&r;for(r=0;n;n/=b)*--p=n%b+48+(n%b>9)*39;puts(p);}

testing:
main(){
  c(65,2);
  c(100,30);
  c(57005, 16);
}

output:
1000001
3a
dead

issues:

0 is printed as empty string.
potential buffer overflows due to abuse of 'int' as a char array...
works with Apple clang v4.0 - your milage may vary with other compilers.

Just to tease you a bit, i've got a working c function in 48 characters, i will release it after i choose a winner :)

Also, it's architecture specific (depends on endianness of system).

Furthermore, puts appends a newline, so your outputs are vertical.

The 48 char version is out now, thanks to Wug, but its far less interesting/dangerous than yours. The code that gcc produces is remarkably safe, since r is the last value on the stack and the stack isnt used after that, all you are overwriting is uninitialized stack space. you could even get rid of the 1+, so you would ensure there is always a 0 byte at the end of the string. @Wug: he doesn't print character-wise, so the output is fine.

Python, 81 58 bytes
x=lambda n,b:(n/b and x(n/b,b)or'')+chr(48+n%b+39*(n%b>9))

Usage:
x(100,30) returns '3a', which is 100 in base 30.

some output characters are not from the required alphabet: x(30,36)='~'

3a is 100 in base 30 (3*30+10)

quasimido and @SeanCheshire - both right, a stupid mistake by me (same bug caused both symptoms). Fixed.

PHP, 92 Bytes
Quite new to code-golf, so probably can do better than this (suggestions would be very welcome!)
function b($n,$b){while($n>0){$r=$n%$b;$n=floor($n/$b);$s=($r>9?chr(87+$r):$r).$s;}echo$s;}

With (some) whitespaces:
function b($n,$b)
{
  while ($n>0)
  {
    $r=$n%$b;
    $n=floor($n/$b);
    $s=($r>9?chr(87+$r):$r).$s;
  }
  echo $s;
}

Next time somebody has to -1 my answer, could you please explain why? I am trying to learn here :) No hard feelings!

You could probably shorten it by making the function recursive. Remember, you don't need to print the string, returning it is enough.

C, 48 chars
i(n,b){n?i(n/b,b),putchar(n%b+48+(n%b>9)*39):0;}

input of 0 produces empty string

C, 77 49 chars, prints 0 for zero
I(n,b){putchar(n?i(n/b,b),48+n%b+(n%b>9)*39:48);}

To run, call i for first version, I for second.

@quazimodo: I got this by hax0ring your computer.  It was hard because you had norton, but you'll never catch me because im behind 7 proxies.

youre so 1337! But i need just one more char to print zero as 0 :D

@quasimodo: like this? :D

more like this: c(n,b){n/b&&c(n/b,b);putchar((n%b>9)*39+48+n%b);}. But yours is also nice!

C# – 85 characters
string F(int n,int b){var s="";for(;n>0;n/=b)s=(char)(n%b+(n%b>9?87:48))+s;return s;}

VBA, 99
(70 if you take out the function/endfunction lines)
Function F(a,b)
F="":q=a:Do:c=q Mod b:F=Chr(c+48-39*(c>9))&F:q=Int(q/b):Loop Until q=0
End Function

fixed for case when a=0

Ocaml, 98 or 120
It prints out a leading zero, though. Usage: 16-0xBEEF
let rec(-)b=function|0->"0"|n->b-n/b^String.make 1(Char.chr(n mod b+if n mod b>9 then 55 else 48))

Unfortunately a lot of characters are spent on converting to char then to string :/
This one is correct.
let rec(-)b=function|0->"0"|n->(if 0=n/b then""else b-n/b)^String.make 1(Char.chr(n mod b+if n mod b>9 then 55 else 48))

The strong typing in ocaml is sometimes unfortunate when golfing. Partial application and such somewhat make up for it, though.

CoffeeScript (98 92)
z=(i,b)->a=parseInt(i)%b;return''if 1>i;(z i/b,b)+if a>9then String.fromCharCode(a+87)else a

The compiled (and readable) javascript for the interested:
z = function(i, b) {
  var a;
  a = parseInt(i) % b;
  if (1 > i) {
    return '';
  }
  return (z(i / b, b)) + (a > 9 ? String.fromCharCode(a + 87) : a);
};

What can I say? Unnecessary recursion gets me hot.
This could have been far shorter if I knew a shorter way to floor or convert from ASCII in Coffee-/Javascript. Tips would be greatly appreciated.
Edited to include "parseInt" to save a couple of characters on "Math.floor" and with some rearranging to reduce the "if ... then ..."s. Unfortunately, I don't think there even is a shorthand if in CoffeeScript ( "... ? ... : ..." doesn't work).

parseInt() would be 2 char shorter of Math.floor, and I believe would have the same effect

you don't need Math.floor if you are using String.fromCharCode to print the numbers, also you can probably shorten the code a bit by using shortcut operators instead of ifs.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Transposed, primes, oh my!
The task is simple: your program reads an integer as an input, and prints whether it is a prime or not. You can print "yes/no", "true/false" or anything what unambiguously identifies the result.
The challenge is, the code has to work with its rows and columns transposed.
To exclude the obvious solution (shortest "simple" solution repeated vertically char-by-char with the use of comments), the metric is a little bit different from the usual code-golf:
Because formatting is very important in this challenge, the code size is measured in the area of the smallest rectangle the code fits in. In other words, whitespace does count, and the lines should be filled to be of equal length (you don't have to actually do it when you post the solution, for simplicity's sake). For example
int main()
{
    return 0;
}

would have a size of 4*13 = 52, (and obviously it does not fit either of the two criteria: prime detection and transposable.)
Smallest size wins.
You can use any language, and any library function except if the sole purpose of that function is to find, generate, or detect primes.
Edit:
While the winner would probably be the Golfscript solution, I'll award a 50 point bounty for the best C or C++ solution!

Your rectangle metric fails to discourage the obvious solution -- better would be to take the longest sidelength.  Though, this would reduce the GS answer to having score 4.

You are right. The next transposed problem should have a different metric and forbid symmetrical solutions. However I think even then there will be someone who circumvents the rules or at least finds a solution the QA was not expecting when composing the rules.

GolfScript, 13 × 1
~.,2>{1$\%!}?

GolfScript strikes again!
Repeats the input if it is prime, otherwise prints the input concatenated with its smallest proper divisor.  Yes, I know that's stretching the definition of "anything what unambiguously identifies the result", but doing anything fancier would cost a few extra characters.  If you want nicer output, appending the three characters ;]! to the code yields 1 for primes and 0 for composite numbers.
The algorithm is really inefficient, just brute force trial division from 2 to n−1.
Most GolfScript operators are only single characters, so this code works just as well transposed.  Annoyingly, though, the assignment operator : doesn't allow whitespace between itself and its target, so I had to do this entirely without variables.

Wrt "anything fancier would cost a few extra characters" - you can get a GolfScript-style Boolean for only 2.

@Peter: You mean something like my edit above, only without the !?  Or did you have something fancier in mind?

I was thinking ) before the , so that it always finds a divisor and = at the end.

: followed by newline, assigns to the newline character - so it's not that whitespace is not allowed, it's just that the whitespace is what gets assigned to

@gnibbler: Technically, we're both right. : does not allow whitespace, or anything else, between itself and its target: whatever immediately follows it, whether whitespace or any other token (yes, even numbers, strings or code blocks), is what gets assigned to.  However, whitespace is what the official documentation specifically warns about, and for good reason -- since in most other places, adding whitespace between tokens in GolfScript does nothing (normally, unless it's been assigned to...).

C, 2*70 2*60
Prints y for primes, nothing otherwise.
EDIT: Changed code to save 10 chars. Must be run without paramters (so m=1).
main(m,n){for(scanf("%d",&n);n%++m&&n>1;);n-m||puts("y");}/*
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/

The method for handling the transposition is quite generic, and can be applied to any program.
It's based on converting this:
abcd/*
\\\\*/

To this:
a\
b\
c\
d\
/*
*/

And both mean simply abcd.

wow, clever misuse of line concatenation :)

This is a golf/puzzles site.  There is no such thing as misuse.

@boothby, I guess he means abuse. But I don't argue with compliments.

C - 13x13
Reads the input from stdin and prints a 1 for prime and a 0 for not prime.
////m(i;(a=)<
////aans")a;2
//:Di)tc%;;p)
//O n{ adfau+
main//bn"o%t4
(a){///f,r-c8
int b///&(-h)
;scanf///bba;
("%d",&///;r}
a);for(b///(
=a;a%--b;//(
);putchar((b
<2)+48);}

edit: compiles with gcc and clang now, other compilers weren't tested

C, 12x12 chars
A two-dimensional solution, unlike my other answer, based on the same code (and like it, prints y for prime, nothing for composite).
The structure is similar to Quasimodo's answer, but my code is shorter, and I think my usage of comemnts is a bit more efficient, so I can fit 12x12.
////m()s";np
////am{c%n>u
////i,fad%1t
////nnon"+;s
main//rf,+)(
(m,n//((&m;"
){for(//n&ny
scanf(//)&-"
"%d",&n)//m)
;n%++m&&//|;
n>1;);n-m||
puts("y"); }

Perl, 14 x 14
I think I'm getting the hang of this. Specify the number as a command line argument, outputs 0 or 1. Probably more room for improvement.
$   n=pop;$p|=
 !  ($n%$_)for
  2 ..$n/2;
   print!$p+m~
n(.r
=$.i
pn$n
o%nt
p$/!
;_2$
$);p
pf +
|o m
=r ~

Q
Abused comments for a symmetric, character inefficient solution.
/{/////////////////////////////////
{(~)any 0=mod[x;2+(!)x-2]}"I"$(0:)0
/~
/)
/a
/n
/y
/
/0
/=
/m
/o
/d
/[
/x
/;
/2
/+
/(
/!
/)
/x
/-
/2
/]
/}
/"
/I
/"
/$
/(
/0
/:
/)
/0

Takes input from STDIN, returns a boolean.

Noticed the sqrt in there. When looking for primes in code-golf, it's usually advantageous to (wastefully) divide all the way up to n rather than stopping at sqrt n.

Very true, thanks. I haven't had a chance to try and get a better score yet.

You should include a score in your answer

05AB1E, 1x5 1x3 (5 3 bytes)
This isn't one big program; each line is a separated alternative program to tackle the prime check (without using the prime builtin).
ÑPQ
ÒgΘ
ÒQP
ÕαΘ
fQO
fs¢
f`Q

-2 bytes thanks to Grimy.
Whitespaces in between lines are no-ops in 05AB1E, and since I only use 1-byte commands, this works fine after transposing.
Outputs 1/0 for truthy/falsey respectively.
Try the first one online or verify some more test cases for all of them (with eval builtin .V).
Transposed: Try the first one online.
Explanation:
Ñ    # Get a list of all divisors of the (implicit) input-integer
     # (which would be only 1 and the integer itself for primes)
 P   # Take the product of that list
  Q  # And check if it's equal to the (implicit) input-integer

Ò    # Get a list of all prime factors of the (implicit) input-integer
 g   # Get the amount of those prime factors by taking the length of the list
  Θ  # Check if that's equal to 1 (so only itself is a prime factor)

Ò    # Get a list of all prime factors of the (implicit) input-integer including duplicates
 Q   # Check for each if it's equal to the (implicit) input-integer
     # (1 if truthy; 0 if falsey)
  P  # Take the product of those checks (resulting in either 1 or 0 as well)

Õ    # Get the Euler totient of the (implicit) input-integer
 α   # Take the absolute difference with the (implicit) input-integer
  Θ  # Check if that's equal to 1

f    # Get a list of all prime factors of the (implicit) input-integer without duplicates
 Q   # Check for each if it's equal to the (implicit) input-integer
  O  # And take the sum of that (resulting in either 1 or 0)

f    # Get a list of all prime factors of the (implicit) input-integer without duplicates
 s   # Swap to get the (implicit) input-integer
  ¢  # And count how many time it occurs in the list

f    # Get a list of all prime factors of the (implicit) input-integer without duplicates
 `   # Dump all the content of this list onto the stack
  Q  # Check if the top two values are equal, or if only a single value is present, it will
     # use the (implicit) input-integer as second value

     # For all these program the same applies at the end:
     # (implicitly output the result with trailing newline)

NOTE: If only a truthy/falsey value is valid, and it doesn't necessary has to be distinct, either Òg or Õα could be used as valid 2-byters, since only 1 is truthy in 05AB1E, and everything else is falsey: Try both of them for some test cases.
If builtins were allowed, a single p would have sufficed: Try it online or verify some more test cases.

ÑPQ or ÒgΘ or ÒQP for 3 bytes. (Ñ and Ò both have purposes other than “to find, generate, or detect primes”, so they’re not included in the ban, by my reading).

More 3-byters: ÕαΘ, fQO, fs¢, f`Q

@Grimy Ah, can't believe I hadn't thought about the divisors or prime factor builtins.. I answered too quickly I guess. Didn't knew about Õα, though! That's a pretty nice one.

APL (Dyalog Unicode), 10x11
{⍵∊∘.×⍨1↓⍳⍵
 ∊
 ∘
 .
 ×
 ⍨
 1
 ↓
 ⍳
 ⍵         }

Try it online!
Corrected the function to comply with the specifications. Thanks @Adám for the heads-up.
Returns 0 for truthy, 1 for falsy.
How
{⍵∊∘.×⍨1↓⍳⍵ ⍝ Dfn. everything below this is a noop up until closing the brace
         ⍳⍵ ⍝ Range [1..arg]
       1↓   ⍝ Dropping the first element (yields [2..arg])
   ∘.×⍨     ⍝ Multiplication table for each element in the vector
 ⍵∊         ⍝ Check if the argument is in the table.

The transposed version is the exact same.

Runic Enchantments, 7×1
v̀i'PA@

Try it online!
Runic cares not for your feeble attempts at source rearrangement! Conforming to the requirement of still functioning after having the source transposed cost +3 bytes (+2 rectangle width) for the reflection modifier and entry point.
Transposed or transposed, but leaving the combining character attached to its parent.

dzaima/APL, 8×9 = 72
{t←0,1↓⍳⍵
 ←⍵∊∘.×⍨t
 0∊
 ,∘
 1.
 ↓×
 ⍳⍨
 ⍵t     }

Try the original or transposed!

Python 3, 28 x 28 size
lambda i:i>1 and           \
all(i%j for j in range(2,i))
ml="""                     "
b("                        "
di"                        "
a%"
 j
i
:f
io
>r
1
 j
a
ni
dn

 r
 a
 n
 g
 e
 (
 2
 ,
 i
 )
\)"""

Try it online!

JavaScript (Node.js), 26 25x5
n=>!( P/**//*-
= * P =* /** -         r
>**/= r=>n%--r?P(r):~-r)(
/*////=  %  *        /*/n
*1 )//>*/   /        *//)

Try it online!
Transposed:
n=>/*
= **1
>**/
! //)
(P=//
   //
P=r=>
/*= *
* > /
*/n%
/*%
/*-
* -*/
--r
  ?
  P
  (
  r
  )
  :
  ~
  -/*
  r*/
 r)//
  (n)

Try it online!

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Domino Effect Problem
Last week we had a programming contest in my university and I am very curious about one of the problems , one which only one team (but from another city) was able to solve. Maybe its not that hard, but I cant find any solutions that will take less than a second of execution time. The problem is the following:
Problem
You have N domino tiles separated by different amounts (integer values that are given to you) and you know the height H of these tiles (all have the same height). They are all placed standing up so that if you push one it falls in the direction of the next one. This way, if tile I is close enough (H or less) to tile I+1, the first one will push the second one when it is pushed down, producing the domino effect. Suppose that not all the distances that separate the tiles are smaller than H, what's the minimum amount of moves you need to make in order to have all the distances be at most H? You can't move the first nor the last tile. Print a falsey value if it is not possible.
Note: You are only allowed to move integer amounts and only to spots on the line defined by tile i-1 and tile i+1. This means you cant grab one and place it wherever you want.
Here are the input sizes: (3 ≤ N ≤ 1000) (1 ≤ H ≤ 50)  and the distances (1 ≤ Di ≤ 100 for i = 1, 2, ..., N-1). Someone uploaded it to SPOJ recently

Input:
N H
d1 d2 d3 d4 ... d(n-1)
Output:
Minimum amount of moves.

Sample

Input1
8 3
2 4 4 1 4 3 2
Output1
3

Sample2

Input2
10 2
1 2 2 2 2 2 2 2 3
Output2
8

Sample3

Input3
5 2
2 2 2 2
Output3
0

Sample4

Input4
5 3
1 6 2 4
Output4
-1 (NOT POSSIBLE)

I have only found a good solution for two cases (Pseudo-Code):
D=sum_of_all_distances
MaxPossible=(N-1)*H

if D==MaxPossible and there is no di such that di>H
    Answer=0

else if D>MaxPossible
    Answer=-1

Some harder test cases: 10 2 \ 1 1 3 2 2 2 2 2 3 should output 8, and 8 3 \ 4 4 1 1 1 4 4 should output 4.

While this is an interesting problem (my initial hunch is that DP is the solution, but I'd have to think about it), the purpose of this site is effectively to run mini-contests. That's why the FAQ says that each question should have an objective winning condition. Can you select a suitable condition which allows you to pick the "best" of the correct answers?

@PeterTaylor  DP?  http://www.abbreviations.com/DP

@DavidCarraher, dynamic programming

How about the first correct answer wins?

You could make the problem specification a bit clearer. What exactly is a "move" – you take one tile out of the chain and put it in some other empty place? Or, you just push a single stone closer to one of its neighbours? Can you move by arbitrary distances, or just in steps of one? — BTW, real domino tiles can not be placed that far apart and  support a chain reaction, it's actually more like √½ ⋅ H.

You are right, i will edit it to specify what "move" means. And you are also right about the real distance that pushes the next tile down, but for this problem H is ok. Just out of curiosity, are you certain about sqrt(.5) ?

@PeterTaylor some friends also said DP, how would you do it?

Python
N, H = map(int, raw_input().split())
D = map(int, raw_input().split())

# map from (number of dominoes, distance to last domino) to
# the number of moves needed to adjust the first number of dominoes
# exactly that far.
M = {}
M[1,0] = 0

for i in xrange(2, N+1):      # i = number of dominos to try
  for d in xrange(H*(i-1)+1):
    M[i,d] = 1e9
  for d in xrange(H*(i-1)+1): # position of last domino
    for e in xrange(1, H+1):  # distance from last domino to previous one
      if d-e > H*(i-2): continue
      if d-e < 0: continue
      if sum(D[:i-1]) == d:
        # don't move last domino, arrange rest
        M[i,d] = min(M[i,d], M[i-1,d-e])
      else:
        # arrange rest, move last domino to right location
        M[i,d] = min(M[i,d], 1 + M[i-1,d-e])

print M.get((N,sum(D)), -1)

Standard dynamic programming.  Runs pretty much instantaneously on the example inputs.  How big a problem do we have to solve in under a second?

here are the input sizes: (3 ≤ N ≤ 1000) (1 ≤ H ≤ 50)  and the distances (1 ≤ Di ≤ 100 for i = 1, 2, ..., N-1). Someone uploaded it to SPOJ recently http://www.spoj.pl/problems/TAP2012E/

wow, you have less than 20 lines! thats awesome, may be you can test it in that spoj link

Well it times out as a SPOJ submission.  It takes a few seconds when I try it at N=500.

I tried in Perl which tries immediate tile distance adjustment and then cascading movements to get required distance

Execution syntax perl programName N H d1 d2 ... dn-1

Test cases sample: perl domino_slider.pl 8 3 2 4 4 1 4 3 2 output :3

use subs /dominochecker distancechecker subcheckright subcheckleft RigidMode/;

## Receive Input Tile Height D1 D2 ... Dn-1
$Tiles=$ARGV[0];
$Height=$ARGV[1];
$loop_count=0;
for $i (2...$#ARGV){
   $distance[$loop_count]=$ARGV[$i];
   $loop_count++;
}

$loop_count=$move=0;

sub dominochecker {
   $lc=0;$retflag=0;
   while ($lc<$Tiles-1) {
     if ($distance[$lc]>$Height) {
         $retflag=1;
     }
     $lc++;
   }
   return $retflag;
}

sub subcheckleft {
   $lc=0;$retflag=0;$c=$_[0];
   while ($lc<$c) {
     if ($distance[$lc]>$Height) {
         $retflag=1;
     }
     $lc++;
   }
   return $retflag;
}

sub subcheckright {
   $retflag=0;$c=$_[0];
   while ($c<$Tiles-1) {
     if ($distance[$c]>$Height) {
         $retflag=1;
     }
     $c++;
   }
   return $retflag;
}

$loop_count=$move=0;

if (dominochecker==0) { ## if already in Domino Effect
print "\n $move \n";
exit;
}

sub RigidMode{
$loopend=$_[0];
$loop_count_local=0;
while ($loop_count_local<$loopend) {
  if ($distance[$loop_count_local]<=$Height) {
    $loop_count_local++;
  } else {
    if ($distance[$loop_count_local-1]<$Height && $loop_count_local+1 !=1 && defined($distance[$loop_count_local-1]) ) {
       $move++;
       $available=$Height-$distance[$loop_count_local-1];
       $required=$distance[$loop_count_local]-$Height;
       if($available<=$required) {
       $distance[$loop_count_local-1]=$distance[$loop_count_local-1]+$available;
       $distance[$loop_count_local]=$distance[$loop_count_local]-$available;
       }else{
       $distance[$loop_count_local-1]=$distance[$loop_count_local-1]+$required;
       $distance[$loop_count_local]=$distance[$loop_count_local]-$required;
       }
       $loop_count_local=0;
    }elsif($distance[$loop_count_local+1]<$Height && $loop_count_local+2 !=$Tiles && defined($distance[$loop_count_local+1]) ){
       $available=$Height-$distance[$loop_count_local+1];
       $required=$distance[$loop_count_local]-$Height;
       if($available<=$required) {
       $distance[$loop_count_local+1]=$distance[$loop_count_local+1]+$available;
       $distance[$loop_count_local]=$distance[$loop_count_local]-$available;
       }else{
       $distance[$loop_count_local+1]=$distance[$loop_count_local+1]+$required;
       $distance[$loop_count_local]=$distance[$loop_count_local]-$required;
       }
       $move++;
       $loop_count_local=0;
    }
    else{
    $loop_count_local++;
    }
  }
}
}

RigidMode($Tiles-1);

if (dominochecker==0) {
    print "\n $move \n";
    exit;
}else{
    $loop_count=$move=0;
    for $i (2...$#ARGV){
        $distance[$loop_count]=$ARGV[$i];
        $loop_count++;
    }
    $loop_count=$move=0;
    while ($loop_count<$Tiles-1) {
    if ($distance[$loop_count]<$Height) {
       $available=$Height-$distance[$loop_count];
       if (subcheckleft($loop_count)>0){
         $move++ if $distance[$loop_count-1]-$available>0;
         $distance[$loop_count]=$Height if $distance[$loop_count-1]-$available>0 ;
         $distance[$loop_count-1]=$distance[$loop_count-1]-$available if $distance[$loop_count-1]-$available>0;
         RigidMode($loop_count+1);
         $loop_count=0 if $distance[$loop_count-1]-$available>0;
         $loop_count++ if $distance[$loop_count-1]-$available<=0;
       }elsif(subcheckright($loop_count)>0) {
         $move++ if $distance[$loop_count+1]-$available>0;
         $distance[$loop_count]=$Height if $distance[$loop_count+1]-$available>0;
         $distance[$loop_count+1]=$distance[$loop_count+1]-$available if $distance[$loop_count+1]-$available>0;
         RigidMode($loop_count+1);
         $loop_count=0 if $distance[$loop_count+1]-$available>0;
         $loop_count++ if $distance[$loop_count+1]-$available<=0;
       }else{
         $loop_count++;
       }
    }else{
         $loop_count++;
    }
    }
}

if (dominochecker==0) {
    print "\n $move \n";
    exit;
}
else{
    print "\n -1 \n";
    exit;
}

here are the input sizes: (3 ≤ N ≤ 1000) (1 ≤ H ≤ 50) and the distances (1 ≤ Di ≤ 100 for i = 1, 2, ..., N-1). Someone uploaded it to SPOJ recently http://www.spoj.pl/problems/TAP2012E/


text:
Fastest semiprime factorization
Write a program to factorize a semi-prime number in the shortest amount of time.
For testing purposes, use this:
\$38!+1\$ (\$523022617466601111760007224100074291200000001\$)
It is equal to:
\$14029308060317546154181 × 37280713718589679646221\$

While I like the "fastest" bit, since it gives languages like C the advantage over typical codegolfing languages, I do wonder how you will test the results?

If you mean that 12259243 will be used to test how fast the programs are, the results will be so small that you won't get any statistically significant differences.

I added a larger number, thx for the heads up.

@Mr Lister, I'll test it on my own PC.

inb4 someone uses preprocessor abuse to write a 400 exabyte lookup table.

I’ve voted to close this question as it fails to meet our standards on fastest-code challenges (namely details on how each program will be tested and scored)

Python (w/ pypy2 v7.3.1) ~0.9s
Using a Multiple Polynomial Quadratic Sieve. I took this to be a code challenge, so I opted not to use any external libraries (other than the standard log function, I suppose). When timing, the PyPy JIT should be used, as it results in timings 4-5 times faster than that of cPython.
Update (2013-07-29):
Since originally posting, I've made several minor, but significant changes which increase the overall speed by a factor of about 2.5x.
Update (2014-08-27):
As this post is still receiving attention, I've updated my_math.py correcting two errors, for anyone who may be using it:

isqrt was faulty, sometimes producing incorrect output for values very close to a perfect square. This has been corrected, and the performance increased by using a much better seed.
is_prime has been updated. My previous attempt to remove perfect square 2-sprps was half-hearted, at best. I've added a 3-sprp check - a technique used by Mathmatica - to ensure that the tested value is square-free.

Update (2014-11-24):
If at the end of the calculation no non-trivial congruencies are found, the progam now sieves additional polynomials. This was previously marked in the code as TODO.
Update (2020-08-29):
A few improvements resulting in minor performance gains, including:

Calculating the average contributation of the skipped primes, rather than roughly approximating.
Actually sieving powers of the prime factor base. The modular square root of each power can be computed efficiently through use of Hensel Lifting.
Reusing the sieve array in subsequent iterations, rather than creating a new one.

mpqs.py
import math
import my_math
import time

# Multiple Polynomial Quadratic Sieve
# assumes n is composite
def mpqs(n, verbose=False):
  if verbose:
    time1 = time.time()

  root_n = my_math.isqrt(n)
  root_2n = my_math.isqrt(n+n)

  # formula chosen by experimentation
  # seems to be close to optimal for n < 10^50
  bound = int(7.5 * math.log(n, 10)**2)

  prime = []
  mod_root = []
  log_p = []
  num_prime = 0

  # size of the sieve
  x_max = bound * 5
  x_max_2 = x_max+x_max

  # maximum value on the sieved range
  m_val = (x_max * root_2n) >> 1

  # find a number of small primes for which n is a quadratic residue
  pg = my_math.primes()
  p = pg.next()
  while p < bound or num_prime < 3:

    # legendre (n|p) is only defined for odd p
    if p > 2:
      leg = my_math.legendre(n, p)
    else:
      leg = n & 1

    if leg == 1:
      prime += [p]
      log_p += [math.log(p, 10)]
      r = int(my_math.mod_sqrt(n, p))
      roots = [r]
      q = p
      while q < x_max:
        # find all square roots mod p^n via Hensel Lifting
        r = int((r + (n - r*r)*my_math.mod_inv(r+r, q))%q)
        #assert r*r%q == n%q
        roots += [r]
        q *= p
      mod_root += [roots]
      num_prime += 1
    elif leg == 0:
      if verbose:
        print 'trial division found factors:'
        print p, 'x', n/p
      return p

    p = pg.next()

  # fudging the threshold down a bit makes it easier to find powers of partial-partial
  # relationships, but it also makes the smoothness check slower. reducing by twice the log
  # of the largest prime in the factor base results in cofactors less than that value squared
  thresh = math.log(m_val, 10) - log_p[-1]*2

  # skip small primes. they contribute very little to the log sum
  # and add a lot of unnecessary entries to the table
  # instead, fudge the threshold down a bit, according to expected number of factors
  min_prime = int(thresh*2)
  sp_idx = my_math.binary_search(prime, min_prime)
  sieve_primes = prime[sp_idx:]

  fudge = sum([log_p[i]/(prime[i]-1) for i in xrange(sp_idx)])

  sums = [fudge]*x_max_2

  if verbose:
    print 'smoothness bound:', bound
    print 'sieve size:', x_max
    print 'log threshold:', thresh
    print 'skipping primes less than:', min_prime

  smooth = []
  used_prime = set()
  partial = {}
  num_smooth = 0
  prev_num_smooth = 0
  num_used_prime = 0
  num_partial = 0
  num_poly = 0
  root_A = my_math.isqrt(root_2n / x_max)

  if verbose:
    print 'sieving for smooths...'
  while True:
    # find an integer value A such that:
    # A is =~ sqrt(2*n) / x_max
    # A is a perfect square
    # sqrt(A) is prime, and n is a quadratic residue mod sqrt(A)
    while True:
      root_A = my_math.next_prime(root_A)
      leg = my_math.legendre(n, root_A)
      if leg == 1:
        break
      elif leg == 0:
        if verbose:
          print 'dumb luck found factors:'
          print root_A, 'x', n/root_A
        return root_A

    A = root_A * root_A

    # solve for an adequate B
    # B*B is a quadratic residue mod n, such that B*B-A*C = n
    # this is unsolvable if n is not a quadratic residue mod sqrt(A)
    b = my_math.mod_sqrt(n, root_A)
    B = (b + (n - b*b) * my_math.mod_inv(b + b, root_A))%A

    # B*B-A*C = n <=> C = (B*B-n)/A
    C = (B*B - n) / A

    num_poly += 1

    # sieve for prime factors
    i = sp_idx
    for p in sieve_primes:
      logp = log_p[i]

      e = 0
      q = p
      while q < x_max:
        inv_A = my_math.mod_inv(A, q)
        # modular root of the quadratic
        a = int(((mod_root[i][e] - B) * inv_A)%q)
        b = int(((q - mod_root[i][e] - B) * inv_A)%q)

        amx = a+x_max
        bmx = b+x_max

        apx = amx-q
        bpx = bmx-q

        k = q
        while k < x_max:
          sums[apx+k] += logp
          sums[bpx+k] += logp
          sums[amx-k] += logp
          sums[bmx-k] += logp
          k += q

        q *= p
        e += 1

      i += 1

    # check for smooths
    x = -x_max
    i = 0
    while i < x_max_2:
      v = sums[i]
      if v > thresh:
        vec = set()
        sqr = []
        # because B*B-n = A*C
        # (A*x+B)^2 - n = A*A*x*x+2*A*B*x + B*B - n
        #               = A*(A*x*x+2*B*x+C)
        # gives the congruency
        # (A*x+B)^2 = A*(A*x*x+2*B*x+C) (mod n)
        # because A is chosen to be square, it doesn't need to be sieved
        sieve_val = (A*x + B+B)*x + C

        if sieve_val < 0:
          vec = {-1}
          sieve_val = -sieve_val

        for p in prime:
          while sieve_val%p == 0:
            if p in vec:
              # keep track of perfect square factors
              # to avoid taking the sqrt of a gigantic number at the end
              sqr += [p]
            vec ^= {p}
            sieve_val = int(sieve_val / p)

        if sieve_val == 1:
          # smooth
          smooth += [(vec, (sqr, (A*x+B), root_A))]
          used_prime |= vec
        elif sieve_val in partial:
          # combine two partials to make a (xor) smooth
          # that is, every prime factor with an odd power is in our factor base
          pair_vec, pair_vals = partial[sieve_val]
          sqr += list(vec & pair_vec) + [sieve_val]
          vec ^= pair_vec
          smooth += [(vec, (sqr + pair_vals[0], (A*x+B)*pair_vals[1], root_A*pair_vals[2]))]
          used_prime |= vec
          num_partial += 1
        else:
          # save partial for later pairing
          partial[sieve_val] = (vec, (sqr, A*x+B, root_A))
      x += 1

      # reset the value for the next go
      sums[i] = fudge
      i += 1

    prev_num_smooth = num_smooth
    num_smooth = len(smooth)
    num_used_prime = len(used_prime)

    if verbose:
      print 100 * num_smooth / num_prime, 'percent complete\r',

    if num_smooth > num_used_prime and num_smooth > prev_num_smooth:
      if verbose:
        print '%d polynomials sieved (%d values)'%(num_poly, num_poly*x_max_2)
        print 'found %d smooths (%d from partials) in %.3f seconds'%(num_smooth, num_partial, time.time()-time1)
        print 'solving for non-trivial congruencies...'

      # set up bit fields for gaussian elimination
      masks = []
      mask = 1
      bit_fields = [0]*num_used_prime
      for vec, vals in smooth:
        masks += [mask]
        i = 0
        for p in used_prime:
          if p in vec: bit_fields[i] |= mask
          i += 1
        mask += mask

      # row echelon form
      col_offset = 0
      null_cols = []
      for col in xrange(num_smooth):
        pivot = col-col_offset == num_used_prime or bit_fields[col-col_offset] & masks[col] == 0
        for row in xrange(col+1-col_offset, num_used_prime):
          if bit_fields[row] & masks[col]:
            if pivot:
              bit_fields[col-col_offset], bit_fields[row] = bit_fields[row], bit_fields[col-col_offset]
              pivot = False
            else:
              bit_fields[row] ^= bit_fields[col-col_offset]
        if pivot:
          null_cols += [col]
          col_offset += 1

      # reduced row echelon form
      for row in xrange(num_used_prime):
        # lowest set bit
        mask = bit_fields[row] & -bit_fields[row]
        for up_row in xrange(row):
          if bit_fields[up_row] & mask:
            bit_fields[up_row] ^= bit_fields[row]

      # check for non-trivial congruencies
      for col in null_cols:
        all_vec, (lh, rh, rA) = smooth[col]
        lhs = lh   # sieved values (left hand side)
        rhs = [rh] # sieved values - n (right hand side)
        rAs = [rA] # root_As (cofactor of lhs)
        i = 0
        for field in bit_fields:
          if field & masks[col]:
            vec, (lh, rh, rA) = smooth[i]
            lhs += list(all_vec & vec) + lh
            all_vec ^= vec
            rhs += [rh]
            rAs += [rA]
          i += 1

        factor = my_math.gcd(my_math.list_prod(rAs)*my_math.list_prod(lhs) - my_math.list_prod(rhs), n)
        if 1 < factor < n:
          break
      else:
        if verbose:
          print 'none found.'
        continue
      break

  if verbose:
    print 'factors found:'
    print factor, 'x', n/factor
    print 'time elapsed: %.3f seconds'%(time.time()-time1)
  return factor

if __name__ == "__main__":
  import argparse
  parser = argparse.ArgumentParser(description='Uses a MPQS to factor a composite number')
  parser.add_argument('composite', metavar='number_to_factor', type=long, help='the composite number to factor')
  parser.add_argument('--verbose', dest='verbose', action='store_true', help="enable verbose output")
  args = parser.parse_args()

  if args.verbose:
    mpqs(args.composite, args.verbose)
  else:
    time1 = time.time()
    print mpqs(args.composite)
    print 'time elapsed: %.3f seconds'%(time.time()-time1)

my_math.py
import math
import mpqs

# primes less than 212
small_primes = [
    2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37,
   41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89,
   97,101,103,107,109,113,127,131,137,139,149,151,
  157,163,167,173,179,181,191,193,197,199,211]

# pre-calced sieve of eratosthenes for n = 2, 3, 5, 7
indices = [
    1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
   53, 59, 61, 67, 71, 73, 79, 83, 89, 97,101,103,
  107,109,113,121,127,131,137,139,143,149,151,157,
  163,167,169,173,179,181,187,191,193,197,199,209]

# distances between sieve values
offsets = [
  10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6,
   6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4,
   2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6,
   4, 2, 4, 6, 2, 6, 4, 2, 4, 2,10, 2]

# tabulated, mod 105
dindices =[
  0,10, 2, 0, 4, 0, 0, 0, 8, 0, 0, 2, 0, 4, 0,
  0, 6, 2, 0, 4, 0, 0, 4, 6, 0, 0, 6, 0, 0, 2,
  0, 6, 2, 0, 4, 0, 0, 4, 6, 0, 0, 2, 0, 4, 2,
  0, 6, 6, 0, 0, 0, 0, 6, 6, 0, 0, 0, 0, 4, 2,
  0, 6, 2, 0, 4, 0, 0, 4, 6, 0, 0, 2, 0, 6, 2,
  0, 6, 0, 0, 4, 0, 0, 4, 6, 0, 0, 2, 0, 4, 8,
  0, 0, 2, 0,10, 0, 0, 4, 0, 0, 0, 2, 0, 4, 2]

max_int = 2147483647

# returns the index of x in a sorted list a
# or the index of the next larger item if x is not present
# i.e. the proper insertion point for x in a
def binary_search(a, x):
  s = 0
  e = len(a)
  m = e >> 1
  while m != e:
    if a[m] < x:
      s = m
      m = (s + e + 1) >> 1
    else:
      e = m
      m = (s + e) >> 1
  return m

# divide and conquer list product
def list_prod(a):
  while len(a) > 1:
    a = [m*n for m,n in zip(a[::2], a[1::2] + [1])]
  return a[0]

# greatest common divisor of a and b
def gcd(a, b):
  while b:
    a, b = b, a%b
  return a

# extended gcd
def ext_gcd(a, m):
  a = int(a%m)
  x, u = 0, 1
  while a:
    x, u = u, x - (m/a)*u
    m, a = a, m%a
  return (m, x, u)

# legendre symbol (a|m)
# note: returns m-1 if a is a non-residue, instead of -1
def legendre(a, m):
  return pow(a, (m-1) >> 1, m)

# modular inverse of a mod m
def mod_inv(a, m):
  return ext_gcd(a, m)[1]

# modular sqrt(n) mod p
# p must be prime
def mod_sqrt(n, p):
  a = n%p
  if p%4 == 3:
    return pow(a, (p+1) >> 2, p)
  elif p%8 == 5:
    v = pow(a << 1, (p-5) >> 3, p)
    i = ((a*v*v << 1) % p) - 1
    return (a*v*i)%p
  elif p%8 == 1:
    # Shanks' method
    q = p-1
    e = 0
    while q&1 == 0:
      e += 1
      q >>= 1

    n = 2
    while legendre(n, p) != p-1:
      n += 1

    w = pow(a, q, p)
    x = pow(a, (q+1) >> 1, p)
    y = pow(n, q, p)
    r = e
    while True:
      if w == 1:
        return x

      v = w
      k = 0
      while v != 1 and k+1 < r:
        v = (v*v)%p
        k += 1

      if k == 0:
        return x

      d = pow(y, 1 << (r-k-1), p)
      x = (x*d)%p
      y = (d*d)%p
      w = (w*y)%p
      r = k
  else: # p == 2
    return a

#integer sqrt of n
def isqrt(n):
  c = (n << 2)/3
  d = c.bit_length()

  a = d>>1
  if d&1:
    x = 1 << a
    y = (x + (n >> a)) >> 1
  else:
    x = (3 << a) >> 2
    y = (x + (c >> a)) >> 1

  if x != y:
    x = y
    y = (x + n/x) >> 1
    while y < x:
      x = y
      y = (x + n/x) >> 1
  return x

# integer cbrt of n
def icbrt(n):
  d = n.bit_length()

  if d%3 == 2:
    x = 3 << d/3-1
  else:
    x = 1 << d/3

  y = (2*x + n/(x*x))/3
  if x != y:
    x = y
    y = (2*x + n/(x*x))/3
    while y < x:
      x = y
      y = (2*x + n/(x*x))/3
  return x

# strong probable prime
def is_sprp(n, b=2):
  if n < 2: return False
  d = n-1
  s = 0
  while d&1 == 0:
    s += 1
    d >>= 1

  x = pow(b, d, n)
  if x == 1 or x == n-1:
    return True

  for r in xrange(1, s):
    x = (x * x)%n
    if x == 1:
      return False
    elif x == n-1:
      return True

  return False

# lucas probable prime
# assumes D = 1 (mod 4), (D|n) = -1
def is_lucas_prp(n, D):
  P = 1
  Q = (1-D) >> 2

  # n+1 = 2**r*s where s is odd
  s = n+1
  r = 0
  while s&1 == 0:
    r += 1
    s >>= 1

  # calculate the bit reversal of (odd) s
  # e.g. 19 (10011) <=> 25 (11001)
  t = 0
  while s:
    if s&1:
      t += 1
      s -= 1
    else:
      t <<= 1
      s >>= 1

  # use the same bit reversal process to calculate the sth Lucas number
  # keep track of q = Q**n as we go
  U = 0
  V = 2
  q = 1
  # mod_inv(2, n)
  inv_2 = (n+1) >> 1
  while t:
    if t&1:
      # U, V of n+1
      U, V = ((U + V) * inv_2)%n, ((D*U + V) * inv_2)%n
      q = (q * Q)%n
      t -= 1
    else:
      # U, V of n*2
      U, V = (U * V)%n, (V * V - 2 * q)%n
      q = (q * q)%n
      t >>= 1

  # double s until we have the 2**r*sth Lucas number
  while r:
    U, V = (U * V)%n, (V * V - 2 * q)%n
    q = (q * q)%n
    r -= 1

  # primality check
  # if n is prime, n divides the n+1st Lucas number, given the assumptions
  return U == 0

## Baillie-PSW ##
# this is technically a probabalistic test, but there are no known pseudoprimes
def is_bpsw(n):
  if not is_sprp(n, 2): return False

  # idea shamelessly stolen from Mathmatica's PrimeQ
  # if n is a 2-sprp and a 3-sprp, n is necessarily square-free
  if not is_sprp(n, 3): return False

  a = 5
  s = 2
  # if n is a perfect square, this will never terminate
  while legendre(a, n) != n-1:
    s = -s
    a = s-a
  return is_lucas_prp(n, a)

# an 'almost certain' primality check
def is_prime(n):
  if n < 212:
    m = binary_search(small_primes, n)
    return n == small_primes[m]

  for p in small_primes:
    if n%p == 0:
      return False

  # if n is a 32-bit integer, perform full trial division
  if n <= max_int:
    p = 211
    while p*p < n:
      for o in offsets:
        p += o
        if n%p == 0:
          return False
    return True

  return is_bpsw(n)

# next prime strictly larger than n
def next_prime(n):
  if n < 2:
    return 2

  n += 1
  if n < 212:
    m = binary_search(small_primes, n)
    return small_primes[m]

  # find our position in the sieve rotation via binary search
  x = int(n%210)
  m = binary_search(indices, x)
  i = int(n + (indices[m] - x))

  # adjust offsets
  offs = offsets[m:] + offsets[:m]
  while True:
    for o in offs:
      if is_prime(i):
        return i
      i += o

# an infinite prime number generator
def primes(start = 0):
  for n in small_primes[start:]: yield n
  pg = primes(6)
  p = pg.next()
  q = p*p
  sieve = {221: 13, 253: 11}
  n = 211
  while True:
    for o in offsets:
      n += o
      stp = sieve.pop(n, 0)
      if stp:
        nxt = n/stp
        nxt += dindices[nxt%105]
        while nxt*stp in sieve:
          nxt += dindices[nxt%105]
        sieve[nxt*stp] = stp
      elif n < q:
        yield n
      else:
        sieve[q + dindices[p%105]*p] = p
        p = pg.next()
        q = p*p

# true if n is a prime power > 0
def is_prime_power(n):
  if n > 1:
    for p in small_primes:
      if n%p == 0:
        n /= p
        while n%p == 0: n /= p
        return n == 1

    r = isqrt(n)
    if r*r == n:
      return is_prime_power(r)

    s = icbrt(n)
    if s*s*s == n:
      return is_prime_power(s)

    p = 211
    while p*p < r:
      for o in offsets:
        p += o
        if n%p == 0:
          n /= p
          while n%p == 0: n /= p
          return n == 1

    if n <= max_int:
      while p*p < n:
        for o in offsets:
          p += o
          if n%p == 0:
            return False
      return True

    return is_bpsw(n)
  return False

max_trial = 1e10
max_pollard = 1e22

def factor(n):
  if n < max_trial:
    return factor_trial(n)
  for p in small_primes:
    if n%p == 0:
      return [p] + factor(n/p)
  if is_prime(n):
    return [n]
  if n < max_pollard:
    p = pollard_rho(n)
  else:
    p = lenstra_ecf(n) or mpqs.mpqs(n)
  return factor(p) + factor(n/p)

def factor_trial(n):
  a = []
  for p in small_primes:
    while n%p == 0:
      a += [p]
      n /= p
  i = 211
  while i*i < n:
    for o in offsets:
      i += o
      while n%i == 0:
        a += [i]
        n /= i
  if n > 1:
    a += [n]
  return a

def pollard_rho(n):
  # Brent's variant
  y, r, q = 0, 1, 1
  c, m = 9, 40
  g = 1
  while g == 1:
    x = y
    for i in range(r):
      y = (y*y + c) % n
    k = 0
    while k < r and g == 1:
      ys = y
      for j in range(min(m, r-k)):
        y = (y*y + c) % n
        q = q*abs(x-y) % n
      g = gcd(q, n)
      k += m
    r *= 2
  if g == n:
    ys = (ys*ys + c) % n
    g = gcd(n, abs(x-ys))
    while g == 1:
      ys = (ys*ys + c) % n
      g = gcd(n, abs(x-ys))
  return g

def ec_add((x1, z1), (x2, z2), (x0, z0), n):
  t1, t2 = (x1-z1)*(x2+z2), (x1+z1)*(x2-z2)
  x, z = t1+t2, t1-t2
  return (z0*x*x % n, x0*z*z % n)

def ec_double((x, z), (a, b), n):
  t1 = x+z; t1 *= t1
  t2 = x-z; t2 *= t2
  t3 = t1 - t2
  t4 = 4*b*t2
  return (t1*t4 % n, t3*(t4 + a*t3) % n)

def ec_multiply(k, p, C, n):
  # Montgomery ladder algorithm
  p0 = p
  q, p = p, ec_double(p, C, n)
  b = k >> 1
  while b > (b & -b):
    b ^= b & -b
  while b:
    if k&b:
      q, p = ec_add(p, q, p0, n), ec_double(p, C, n)
    else:
      q, p = ec_double(q, C, n), ec_add(p, q, p0, n),
    b >>= 1
  return q

def lenstra_ecf(n, m = 5):
  # Montgomery curves w/ Suyama parameterization.
  # Based on pseudocode found in:
  # "Implementing the Elliptic Curve Method of Factoring in Reconfigurable Hardware"
  # Gaj, Kris et. al
  # http://www.hyperelliptic.org/tanja/SHARCS/talks06/Gaj.pdf
  # Phase 2 is not implemented.
  B1, B2 = 8, 13
  for i in range(m):
    pg = primes()
    p = pg.next()
    k = 1
    while p < B1:
      k *= p**int(math.log(B1, p))
      p = pg.next()
    for s in range(B1, B2):
      u, v = s*s-5, 4*s
      x = u*u*u
      z = v*v*v
      t = pow(v-u, 3, n)
      P = (x, z)
      C = (t*(3*u+v) % n, 4*x*v % n)
      Q = ec_multiply(k, P, C, n)
      g = gcd(Q[1], n)
      if 1 < g < n: return g
    B1, B2 = B2, B1 + B2

if __name__ == "__main__":
  import argparse
  import time
  parser = argparse.ArgumentParser(description='Uses a various methods to factor a composite number')
  parser.add_argument('composite', metavar='number_to_factor', type=long, help='the composite number to factor')
  args = parser.parse_args()

  time1 = time.time()
  print factor(args.composite)
  print 'time elapsed: %.3f seconds'%(time.time()-time1)

Sample I/O:
$ pypy mpqs.py --verbose 523022617466601111760007224100074291200000001
smoothness bound: 14998
sieve size: 74990
log threshold: 18.7325510316
skipping primes less than: 37
sieving for smooths...
230 polynomials sieved (34495400 values)
found 849 smooths (242 from partials) in 0.786 seconds
solving for non-trivial congruencies...
factors found:
37280713718589679646221 x 14029308060317546154181
time elapsed: 1.011 seconds

Note: not using the --verbose option will give slightly better timings:
$ pypy mpqs.py 523022617466601111760007224100074291200000001
37280713718589679646221
time elapsed: 0.902 seconds

Basic Concepts
In general, a quadratic sieve is based on the following observation: any odd composite \$n\$ may be represented as:
\$n=(x+d)(x-d)=x^2-d^2\Rightarrow d^2=x^2-n\$
This is not very difficult to confirm. Since \$n\$ is odd, the distance between any two cofactors of \$n\$ must be even \$2d\$, where \$x\$ is the mid point between them. Moreover, the same relation holds for any multiple of \$n\$
\$abn=(ax+ad)(bx-bd)=abx^2-abd^2\Rightarrow abd^2=abx^2-abn\$
Note that if any such \$x\$ and \$d\$ can be found, it will immediately result in a (not necessarily prime) factor of \$n\$, since \$x+d\$ and \$x-d\$ both divide \$n\$ by definition. This relation can be further weakened - at the consequence of allowing potential trivial congruencies - to the following form:
\$d^2\equiv x^2\mod n\$
So in general, if we can find two perfect squares which are equivalent mod \$n\$, then it's fairly likely that we can directly produce a factor of \$n\$ a la \$\gcd(x±d,n)\$. Seems pretty simple, right?
Except it's not. If we intended to conduct an exhaustive search over all possible \$x\$, we would need to search the entire range from \$\sqrt{n}\$ to \$\sqrt{2n}\$, which is marginally smaller than full trial division, but also requires an expensive is_square operation each iteration to confirm the value of \$d\$. Unless it is known beforehand that \$n\$ has factors very near \$\sqrt{n}\$, trial division is likely to be faster.
Perhaps we can weaken this relation even more. Suppose we chose an \$x\$, such that for
\$y\equiv x^2\mod n\$
a full prime factorization of \$y\$ is readily known. If we had enough such relations, we should be able to construct an adequate \$d\$, if we choose a number of \$y\$ such that their product is a perfect square; that is, all prime factors are used an even number of times. In fact, if we have more such \$y\$ than the total number of unique prime factors they contain, a solution is guaranteed to exist; It becomes a system of linear equations. The question now becomes, how do we chose such \$x\$? That's where sieving comes into play.
The Sieve
Consider the polynomial:
\$y(x)=x^2-n\$
Then for any prime \$p\$ and integer \$k\$, the following is true:
\$y(x+kp)=(x+kp)^2-n\\y(x+kp)=x^2+2xkp+(kp)^2-n\\y(x+kp)=y(x)+2xkp+(kp)^2\equiv y(x)\mod p\$
This means that after solving for the roots of the polynomial mod \$p\$ - that is, you've found an \$x\$ such that \$y(x)\equiv 0\mod p\$, ergo \$y\$ is divisible by \$p\$ - then you have found an infinite number of such \$x\$. In this way, you can sieve over a range of \$x\$, identifying small prime factors of \$y\$, hopefully finding some for which all prime factors are small. Such numbers known as \$k-smooth\$, where \$k\$ is the largest prime factor used.
There's a few problems with this approach, though. Not all values of \$x\$ are adequate, in fact, there's only very few of them, centered around \$\sqrt{n}\$. Smaller values will become largely negative (due to the \$-n\$ term), and larger values will become too large, such that it is unlikely that their prime factorization consists only of small primes. There will be a number of such \$x\$, but unless the composite you're factoring is very small, it's highly unlikely that you'll find enough smooths to result in a factorization. And so, for larger \$n\$, it becomes necessary to sieve over multiple polynomials of a given form.
Multiple Polynomials
So we need more polynomials to sieve? How about this:
\$y(x)=(Ax+B)^2-n\$
That'll work. Note that \$A\$ and \$B\$ could literally be any integer value, and the math still holds. All we need to do is choose a few random values, solve for the root of the polynomial, and sieve the values close to zero. At this point we could just call it good enough: if you throw enough stones in random directions, you're bound to break a window sooner or later.
Except, there's a problem with that too. If the slope of the polynomial is large at the x-intercept, there'll only be a few suitable values to sieve per polynomial. It'll work, but you'll end up sieving a whole lot of polynomials before you get what you need. Can we do better?
We can do better. An observation, as a result of Montgomery is as follows: if \$A\$ and \$B\$ are chosen such that there exists some \$C\$ satisfying
\$B^2-n=AC\$
then the entire polynomial can be rewritten as
\$y(x)=(Ax+B)^2-n=(Ax)^2+2ABx+B^2-n=A(Ax^2+2Bx+C)\$
Furthermore, if \$A\$ is chosen to be a perfect square, the leading \$A\$ term can be neglected while sieving, resulting in much smaller values, and a much flatter curve. For such a solution to exist, \$n\$ must be a quadratic residue mod \$\sqrt{A}\$, which can be known immediately by computing the Legendre symbol:
\$(n|\sqrt{A})=1\$. Note that in order to solve for \$B\$, a complete prime factorization of \$\sqrt{A}\$ needs to be known (in order to take the modular square root \$\sqrt{n}\mod\sqrt{A}\$), which is why \$\sqrt{A}\$ is typically chosen to be prime.
It can then be shown that if \$A\approx\frac{\sqrt{2n}}{M}\$, then for all values of \$x\in[-M,M]\$:
\$|y(x)|\le\frac{M\sqrt{2n}}{2}\$
And now, finally, we have all the components necessary to implement our sieve. Or do we?
Powers of Primes as Factors
Our sieve, as described above, has one major flaw. It can identify which values of \$x\$ will result in a \$y\$ divisible by \$p\$, but it cannot identify whether or not this \$y\$ is divisible by a power of \$p\$. In order to determine that, we would need to perform trial division on the value to be sieved, until it is no longer divisible by \$p\$.

Edit: This is incorrect. The roots of \$n\$ mod \$p^k\$ can be computed directly from the roots mod \$p\$ through the use of Hensel Lifting. This current implementation does precisely this.

We seemed to have reached an impasse: the whole point of the sieve was so that we didn't have to do that. Time to check the playbook.
\$\ln(a\cdot b\cdot c\cdot d\cdot\ldots)=\ln(a)+\ln(b)+\ln(c)+\ln(d)+\ln(\ldots)\$
That looks pretty useful. If the sum of the \$\ln\$ of all of the small prime factors of \$y\$ is close to the expected value of \$\ln(y)\$, then it's almost a given that \$y\$ has no other factors. In addition, if we adjust the expected value down a little bit, we can also identify values as smooth which have several powers of primes as factors. In this way, we can use the sieve as a 'pre-screening' process, and only factor those values which are likely to be smooth.
This has a few other advantages as well. Note that small primes contribute very little to the \$\ln\$ sum, but yet they require the most sieve time. Sieving the value 3 requires more time than 11, 13, 17, 19, and 23 combined. Instead, we can just skip the first few primes, and adjust the threshold down accordingly, assuming a certain percentage of them would have passed.
Another result, is that a number of values will be allowed to 'slip through', which are mostly smooth, but contain a single large cofactor. We could just discard these values, but suppose we found another mostly smooth value, with exactly the same cofactor. We can then use these two values to construct a usable \$y\$; since their product will contain this large cofactor squared, it no longer needs to be considered.
Putting it all together
The last thing we need to do is to use these values of \$y\$ construct an adequate \$x\$ and \$d\$. Suppose we only consider the non-square factors of \$y\$, that is, the prime factors of an odd power. Then, each \$y\$ can be expressed in the following manner:
\$y_0=p_0^0\cdot p_1^1\cdot p_2^1\cdots p_n^0\\y_1=p_0^1\cdot p_1^0\cdot p_2^1\cdots p_n^1\\y_2=p_0^0\cdot p_1^0\cdot p_2^0\cdots p_n^1\\y_3=p_0^1\cdot p_1^1\cdot p_2^0\cdots p_n^0\\\vdots\$
which can be expressed in the matrix form:
\$M=\begin{bmatrix}0&1&1&\cdots&0\\1&0&1&\cdots&1\\0&0&0&\cdots&1\\1&1&0&\cdots&0\\\vdots\end{bmatrix}\$
The problem then becomes to find a vector \$v\$ such that \$vM=\vec{0}\mod 2\$, where \$\vec{0}\$ is the null vector. That is, to solve for the left null space of \$M\$. This can be done in a number of ways, the simplest of which is to perform Gaussian Elimination on \$M^T\$, replacing the row addition operation with a row xor. This will result in a number of null space basis vectors, any combination of which will produce a valid solution.
The construction of \$x\$ is fairly straight-forward. It is simply the product of \$Ax+B\$ for each of the \$y\$ used. The construction of \$d\$ is slightly more complicated. If we were to take the product of all \$y\$, we will end up with a value with 10s of thousands, if not 100s of thousands of digits, for which we need to find the square root. This calcuation is impractically expensive. Instead, we can keep track of the even powers of primes during the sieving process, and then use and and xor operations on the vectors of non-square factors to reconstruct the square root.
I seem to have reached the 30000 character limit. Ahh well, I suppose that's good enough. Saved a bunch of bytes by switching to \$MathJax\$.

Well, I never passed algebra in high school ( actually dropped out during the first semester of freshmen year ), but you make it simple to understand from a programmer's perspective. I won't pretend to fully understand it without putting it into practice, but I applaud you. You should consider expanding this post off-site and publishing it, seriously!

I agree. Excellent answer with a great explanation. +1

@primo Your answers to multiple questions on here have been incredibly thorough and interesting. Much appreciated!

@PaulWalls I appreciate the comment :D This question I particularly enjoyed working on. Had I not run out of room, the last section would have been 'Implementation Details' - things that a serious implementation would need to contain, but this one does not (Block Lanczos instead of Gaussian Elimination, ECM factoring of probable smooths, fast modular multiplication, etc.). I also would have liked to mention the various functions in my_math.py, most especially is_prime and next_prime.

@primo Well, it's unfortunate you did run out of room. You've got a knack for explaining topics in a reasonably straightforward manner.

As a last remark, I would like to express my gratitude to Will Ness for awarding the +100 bounty on this question. It was literally his entire reputation.

It seems to be a bit faster now. By the way, but it doesn't work for even semiprimes.

@Dennis Ahh yes, you're right. The Legendre symbol isn't properly defined for the (only) even prime, and thus can't double as trial division for that value.

I just tried mpqs with 1414788616326148885598999113 = 2147483647 × 658812288653553079 but it returns the value 1. I will see if I can work out why it is doing this.

@ArmchairCaver I've updated the code to sieve additional polynomials if no non-trivial congruencies are found on the first attempt.

@primo, first of all, many kudos!!! I've been working on my own QS implementation and can factor 38! + 1 in around 20 minutes (you can find it here).  I've tried larger numbers, and I wanted to see how fast your algorithm could factor 10050120961360479179164300841596861740399588283187.  It took my algo close to 13 hours.

@JosephWood I time about 33s. I do have one idea for further improvement. Using a static log threshold unfortunately rules out most small values (which are actually most likely to be smooth!), whereas the actual curve looks like this: wolfram alpha plot. Using a rolling log threshold would likely find more smooths with less polynomials, although the individual threshold values would need to be fast to approximate to have any sort of speedup.

@primo, 33s... very impressive!!! Your idea about implementing a rolling log threshold could be beneficial, but it could also be detrimental because as you say above "but it also makes the smoothness check slower." This is the problem I ran into (i.e. my smooth checker was extremely slow).  Anywho, have you thought about implementing parallel programming?  That would surely take your algo to the next level.  With parallel programming implemented, you could probably factor 100 digit numbers within a day or so. Again, many kudos!!

This is a wonderful answer. Pypy got faster so I think your code has too now :) 10050120961360479179164300841596861740399588283187 took 15 seconds on my 4 year old PC.

This Python library used your function :)

@StepHen it does. Unfortunately, it uses the original version from 2012, without the speed improvements, and with a bug in in the gaussian elimination (errors when the final column is a pivot column). I attempted to contact the author some time ago, but received no response.

What is the timing with a modern version of pypy?

@Anush The target value times in about 1.38s with PyPy 7.3.1, on the same system used to time the 1.9s originally (about ~27% faster).

That's pretty cool. Well done them.

I may (although not likely before the bounty deadline) attempt to refactor this as a SIQS, which would eliminate the overhead of the while True: next_prime() loop to initialize the next polynomial.

That would be awesome. Bounties are like buses, there is always another one available :)

There seems to be a large prime speedup too which they claim doubles the speed.

This is the large prime version https://www.rieselprime.de/ziki/Self-initializing_quadratic_sieve#Large_prime_variation

What timings do you get for 100000000000000000039000000005700000000000000002223 ?

@Anush that's a bad one, about 9.5s. Regarding the Large Prime variant, the code does this already.

@Anush I appreciate the bounty award, despite failing to beat Mathematica :P. I will try to get the SIQS implemented when I have time (interest I have plenty!).

@primo That would be great!

I tried the code with two random but consecutive primes, and it failed returning a result (it just loops over and over, incrementing polynomials sieved). The two primes are 2449663 and 2449691, the number I tried with is 6000917404133. Why would it fail with that number?

@alexandernst on a value that small, the parameterization will not be very good. Pollard's Rho or Lenstra ECF would both be better options. I have added a general purpose factorization method to my_math.py, which can be used as python my_math.py 6000917404133, or imported.

Are you still working on the SIQS implementation?

@Anush not actively, but I do intend to at some point in time.

@primo We are all willing you on!  And not only because we want to see Mathematica beaten :)

Wolfram Language (Mathematica), 0.34 sec
FactorInteger

Try it online!

Impressive speed! It will be to see if anyone can beat it.

*interesting to see...

Well, your 38!+1 broke my php script, not sure why. In fact, any semi-prime over 16 digits long breaks my script.
However, using 8980935344490257 ( 86028157 * 104395301 ) my script managed a time of 25.963 seconds on my home computer (2.61GHz AMD Phenom 9950). A lot faster than my work computer which was nearly 31 seconds @ 2.93GHz Core 2 Duo.
php - 757 chars incl. new lines
<?php
function getTime() {
    $t = explode( ' ', microtime() );
    $t = $t[1] + $t[0];
    return $t;
}
function isDecimal($val){ return is_numeric($val) && floor($val) != $val;}
$start = getTime();
$semi_prime = 8980935344490257;
$slice      = round(strlen($semi_prime)/2);
$max        = (pow(10, ($slice))-1);
$i          = 3;
echo "\nFactoring the semi-prime:\n$semi_prime\n\n";

while ($i < $max) {
    $sec_factor = ($semi_prime/$i);
    if (isDecimal($sec_factor) != 1) {
        $mod_f = bcmod($i, 1);
        $mod_s = bcmod($sec_factor, 1);
        if ($mod_f == 0 && $mod_s == 0) {
            echo "First factor = $i\n";
            echo "Second factor = $sec_factor\n";
            $end=getTime();
            $xtime=round($end-$start,4).' seconds';
            echo "\n$xtime\n";
            exit();
        }
    }
    $i += 2;
}
?>

I'd be interested to see this same algorithm in c or some other compiled language.

PHP's numbers have only 53 bits precision, roughly 16 decimal digits

Implementing the same algorithm in C++ using 64 bit integers only took about 1.8 seconds to run on my computer. There are several problems with this approach though:

It can't handle large enough numbers.

Even if it could & assuming all numbers, no matter the length, used the same amount of time for trial division, every order of magnitude increase would result in an equivalent amount of time increase. Since your first factor is about 14 orders of magnitude smaller than the given first factor, this algorithm would take over 9 million years to factor the given semiprime.

I'm not the best at math, admittedly, but for very large numbers, standard methods of factoring semi-primes will simply not work (using an elipse, etc.), as far as I know. With that in mind, how could the algorithm itself be improved?

If I knew how to improve the algorithm, I'd be rich! :) I was just observing that the algorithm as is would most likely not solve the stated problem in a measurable time period. I'm still trying to come up with a solution of my own.

The efficiency can be greatly increased by using a pre-calced sieve of eratosthenes. See the is_prime implementation from my solution for details. It uses full trial division whenever the number to be tested can be represented as a 32-bit integer.

@primo No idea what you just said, but I guarantee I'll Google the heck out of it!

The Sieve of Eratosthenes starts with a list of number, then removes all multiples of 2, and then 3, and then 5, and then 7, etc. What remains after the sieve is complete are only prime numbers. This sieve can be 'pre-calced' for a certain number of factors. Because lcm(2, 3, 5, 7) == 210, the pattern of numbers eliminated by these factors will repeat every 210 numbers, and only 48 remain. In that way, you can eliminate 77% of all numbers from trial division, instead of the 50% by taking only odds.

@primo Out of curiosity, how much time did you devote to this? It would have taken me ages to think of this stuff. At the time I wrote this, I was only thinking about how prime numbers were always odd. I didn't attempt to go beyond that and eliminate non-prime odds as well. It seems so simple in retrospect.

@jdstankosky To be honest, I spent almost as much time writing the is_prime and next_prime functions as I did writing the sieve itself.

Hmm, I think PHP must be pretty slow. In C, factoring the number 8980935344490257 by trial division of known primes up to its square root takes only 0.09 seconds on my 1.7 GHz Intel Core i5 laptop. (As a comparison with another algorithm, Shanks's Square Forms Factorization requires only 0.0003 seconds.)

Pari/GP, 0.21s
factor(input())

Pari/GP seems to be slightly more performant in this task than Mathmatica.
Try it online!

Yes yes... But we want some new code :)

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Score a game of Bowling
Your task is to sum up and output one player's score in a game of 10-pin bowling after up to 21 rolls.
The rolls are represented as a sequence of integers in your preferred method of input.
Each integer corresponds to the number of pins that were knocked down in that roll.
Scoring
After each round the number of pins knocked down in that round is counted into the final score.
If a player knocks down all ten pins in the first roll of a round, this is a strike, and the round is over.
Otherwise, the round lasts for one more roll. If the second roll of a round knocks down all the remaining pins, this is a spare.
For each strike there is a bonus equal to the sum of pins knocked down in the two next rolls.
For each spare there is a bonus equal to the number of pins knocked down in the next roll.
The 10th and final round, the player may be granted extra rolls:
In case of a strike, the player gets two more rolls to make up his strike bonus.
In case of a spare, the player gets one more roll.
Examples
Input: 4 3 8 2 7 1 10 7 3 0 10 2 2 10 10 5 4
Output: 131

Input: 10 10 9 1 7 3 2 7 10 1 9 10 7 1 10 10 10
Output: 183

Rules

You may assumed that the input is valid.
As per Mego's comment I have loosened the requirements for the input/output methods to meet our current standard.
Answers in languages that are newer than the challenge are allowed
Shortest code wins!

Do I remember correctly that bonuses don´t stack?

@Titus I'm not exactly sure what you mean, but no, bonuses don't "stack", i.e, for a strike you add the number of pins that are knocked down in the two next rolls, regardless of whether they are strikes or not. So maximum score for one strike is 30 points, and maximum for a whole game is 300.

Do distinct command line arguments qualify as space separated integers?

@Titus sure. This is an old post - Today's consensus on acceptable input methods was not established at this point. Actually, I don't see now why today's standard shouldn't apply to this (including function parameters etc), although I'm not a fan of changing the rules of the challenge retroactively.

@daniero The usual advice is that it's acceptable to loosen the rules to fit modern standards, so long as it doesn't drastically change the challenge.

@Mego sounds reasonable. I've updated the rules.

Do we have to check if the input is valid? Right amount of rolls, right amount of pins per round, etc?

@JarkoDubbeldam No, that was never intended. I will add an clarification

GolfScript, 50 41 characters
~0]-1%~0{\.9>{+1$3$}{@+.9>3$*}if++}10*p];

Another attempt in GolfScript (run it online).
An explanation of the code follows. The solution utilises the stack nature of the problem (consume rolls one after another) but therefore the input has to be reversed.
~0          # Take the input and evaluate to single numbers on the stack. Add zero.
]-1%~       # Reverse the stack (make array, reverse array, dump array)

0           # Start with a sum of zero
{           # Perform this block 10 times (once for each round)
  \         #   Take the next roll
  .9>{      #   If it is a strike
    +       #     Add the value of the roll to the sum
    1$3$    #     and duplicate top two members of the stack (i.e. next two rolls).
  }{        #   ... else ...
    @+      #     Take the next roll and add with first roll in round.
    .9>     #     Does this sum show a spare?
    3$*     #     Get next roll (potential bonus) and multiply with yes/no.
            #     Since we pushed an additional 0 in the beginning
            #     there is a spare roll even for the last round.
  }if       #   endif
  ++        #   Add top three stack entries together
            #   (i.e. sum+2 bonus rolls for strike, sum+rolls+bonus else)
}10*        # Loop ten times

p];         # Sum is top of stack. Print sum and discard any leftover rolls.

Previous version:
~].1>.1>]zip{((.10<{@(0=@+@1>1$9><}*@}10*;]{+}.@**

Python, 116 110 105 103 100 99 characters
z=map(int,raw_input().split())
s=0
exec('s+=sum(z[:2+(z[0]+z[1]>9)]);z=z[2-(z[0]>9):];'*10)

Spending 30 characters on input is irksome.  Suggestions welcome.
Much thanks to Howard for improvements.

You may replace 1+(z[i]!=10) with 2-(z[i]>9) to save one char.

@Howard: Excellent suggestion.  I have incorporated it into my answer.  It saved two characters.

And two more if you remove i completely (set to 0) and instead of i+=... use z=z[2-(z[0]>9)::];

@Howard:  Thanks again.  Saved three characters.

Standards for I/O are generally more flexible now so z=input() should be fine (effectively taking a string representation of a list of ints and evaling it). However full programs should output somewhere (I think this was also the case back then too). As such I believe this may be changed to this 78 byte program

R, 101 bytes
I am not sure why this challenge was bumped, but I like it, so I'll late answer anyways.
f=function(x,s=0,c=10)`if`(c&length(x),f(x[-(0:(x[1]!=10)+1)],sum(x[1:(2+(sum(x[1:2])>9))])+s,c-1),s)

Try it online!
Ungolfed:
f <- function(throws, score = 0, count = 10){
  if(count != 0 & length(throws) != 0){
    IsStrike <- throws[1] == 10
    IsStrikeOrSpare <- sum(throws[1:2]) >= 10
    f(throws[-c(1, 2 * !IsStrike)],
      score + sum(throws[c(1:(2 + IsStrikeOrSpare))]),
      count - 1)
  } else {
    return(score)
  }
}

Recursive function. Takes x as input, which holds the scores. Initialises the scores and counts the amount of rounds thrown.
The if statement checks if 10 rounds are thrown, or if x is empty. If that is the case, the score is returned. Else the function will call itself as follows:
It removes the throws from x, by checking if it is a strike or not. If so, the first entry is removed, else the first two. (S=x[1]!=10) checks for strikes. We remove (-) index 0:S, where S is 1 if it is a strike, and 0 if not. And then we add one: -(0:(x[1]!=10)+1). We pass the shortened x to the next call.
As for the score, this is found by taking x[1:2] if it is a regular turn, and x[1:3] if it is a strike or a spare. We check if sum(x[1:2]) is bigger or equal than 10. If it is a strike, obviously this is the case. If it is a spare, then this works as well. So if this is TRUE, we add x[3] to the sum. This is then added to s.

CoffeeScript (234 215 170)
z=(a)->b=(Number i for i in a.split(' ').reverse());t=0;(r=b.pop();l=b.length;if(9<r)then(t+=r;t+=b[l-1]+b[l-2];)else(f=r+b.pop();t+=f;(t+=b[l-2])if 9<f))for i in[0..9];t

EDIT: A hefty re-write, shamelessly plagiarising Howard's great stack-based approach. I'm confident more can be stripped out for accessing the last element of an array without destroying it...

Ruby, 252 bytes
Accepts input into an array add all elements first, then searches for spare and strike bonus
s,p,t,r=0,0,1,1
o=ARGV
o.each_with_index do |m,n|
y=m.to_i
s+=y
if r<10
p+=y
if p==10&&t==1
r,p=(r+1),0
s+=o[n+1].to_i+o[n+2].to_i
elsif p<10&&t==1
t=2
elsif p<10&&t==2
t,p,r=1,0,(r+1)
elsif p==10&&t==2
t,p,r=1,0,(r+1)
s+=o[n+1].to_i
end end end
puts s

PHP, 82 bytes
for($a=$argv;$r++<10;$i+=$p<10)$s+=(9<$q=$a[++$i+1]+$p=$a[$i])*$a[$i+2]+$q;echo$s;

takes input from command line arguments; run with -nr or test it online.
breakdown
for($a=$argv;       # import arguments
    $r++<10;        # loop through rounds
    $i+=$p<10)          # 6. if no strike, increment throw count again
    $s+=(9<
        $q=$a[++$i+1]+  # 1. increment throw count  2. $q=second throw plus
        $p=$a[$i]       # 3. $p=first throw
        )*$a[$i+2]      # 4. if $q>9 (strike or spare), add third throw to sum
    +$q;                # 5. add first and second throw to sum
echo$s;             # print sum

Perl 5, 65 + 2 = 67 bytes
Requires -ap flags
$\+=(($"=shift@F)<10?$"+=shift@F:10+$F[1])+$F[0]*(9<$")for 0..9}{

Try it online!

Jelly,  36  35 bytes
+\µi©⁵+Ị$ḂḤị;®×Ị¤¡-
;0Ç3ƤFṣ-m€2Fḣ⁵S

A monadic link accepting a list of integers and returning an integer.
Try it online!
How?
Calculates the score of each overlapping run of three bowls as if it were one that started at the beginning of a frame and optionally appends a strike identifier (-1), flattens this resulting list, splits it at the strike identifiers, then discards every second result from each chunk (removing the scores of those runs that did not really start with the start of a frame).
To cater for the final frame a zero is first appended to the input (to allow the 3-wise slicing to allow a frame to start on what was the penultimate bowl) and the resulting scores are truncated to the first ten (to remove the now possible bogus 11th frame) prior to summing them up.
+\µi©⁵+Ị$ḂḤị;®×Ị¤¡- - Link 1, threeBowlEvaluate: list, bowlScores
                    -               e.g. [0,4,6]   [9,1,10]   [0,4,4]  [10,7,9]
 \                  - cumulative reduce with:
+                   -   addition         [0,4,10]  [9,10,20]  [0,4,8]  [10,17,26]
  µ                 - monadic chain separation, call that "left"
     ⁵              - literal ten        10        10         10       10
   i                - first index in left 3         2 (spare)  0        1 (strike)
    ©               - (copy to register for later reuse)
        $           - last two links as a monad (f(x)):
       Ị            -   abs(x) <= 1       0         0          1        1
      +             -   add x             3         2          1        2
         Ḃ          - modulo by 2         1         0          1        0
          Ḥ         - double              2         0          2        0
           ị        - index into left (both 1-indexed and modular)
                    -            ...      4        20          4       26
                  - - literal -1         -1        -1         -1       -1
                 ¡  - repeat:
            ;       - ...action: concatenate
                ¤   - ...number of times: nilad followed by link(s) as a nilad:
             ®      -   z from register   3         2          0        1
               Ị    -   abs(z) <= 1       0         0          1        1
              ×     -   multiply          0         0          0        1 (strike)
                    - ...yielding:        4         20         4        [26,-1]

;0Ç3ƤFṣ-m€2Fḣ⁵S - Main link: list bowlValues
                -                    e.g. [4,3,8,2,7,1,10,7,3,0,10,2,2,10,10,5,4]
 0              - literal zero            0
;               - concatenate             [4,3,8,2,7,1,10,7,3,0,10,2,2,10,10,5,4,0]
   3Ƥ           - for infixes of length 3:
  Ç             -   last link (1) as a monad
                -                         [7,11,17,9,8,11,[20,-1],10,3,12,[14,-1],4,12,[25,-1],[19,-1],9]
     F          - flatten                 [7,11,17,9,8,11,20,-1,10,3,12,14,-1,4,12,25,-1,19,-1,9]
       -        - literal -1              -1
      ṣ         - split at                [[7,11,17,9,8,11,20],[10,3,12,14],[4,12,25],[19],[9]]
          2     - literal two             2
        m€      - modulo slice for €ach   [[7,17,8,20],[10,12],[4,25],[19],[9]]
           F    - flatten                 [7,17,8,20,10,12,4,25,19,9]
             ⁵  - literal ten             10
            ḣ   - head to index           [7,17,8,20,10,12,4,25,19,9] (no effect this time)
              S - sum                     131

JavaScript (ES6),  79 78 72 69  68 bytes
f=([x,y,...r],n=9)=>x+y+~~r[!n|x+y>9?0:f]+(n&&f(x>9?[y,...r]:r,n-1))

Try it online!
Commented
f = (               // f is a recursive function taking:
  [x,               //   x = result of the current roll
      y,            //   y = result of the next roll
         ...r],     //   r[] = remaining results
  n = 9             //   n = remaining number of rounds
) =>                //
  x + y +           // add x + y to the score
  ~~r[              //
    !n |            // if this is the last round
    x + y > 9 ?     // or this is either a spare or a strike:
      0             //   add the result of the next roll to the score
    :               // else:
      f             //   use a dummy index so that nothing is added
  ] + (             //
    n &&            // if n is not equal to 0:
      f(            //   add the result of a recursive call:
        x > 9 ?     //     if this is a strike:
          [y, ...r] //       re-insert y into r[]
        :           //     else:
          r,        //       pass r[] unchanged
        n - 1       //     decrement n
      )             //   end of recursive call
  )                 //

Is the double-bitwise-NOT needed or is it not a bitwise NOT?

@S.S.Anne It's just there to turn undefined into $0$ if there's nothing at the computed index.

Perl, 140?
First attempt:
#!/usr/bin/perl
# usage: ./bowling.pl [list of scores]

@A=@ARGV;{last if(9<$n++);$a=shift@A;$S+=$a;($S+=$A[0]+$A[1])&redo if($a==10);$b=shift@A;$S+=$b;($S+=$A[0])&redo if(10==$a+$b);redo}print$S

Sadly, there are certain cases where it fails. I will come and redo it later.


text:
The shortest code to tell if a number is even or odd
One of my colleagues proposed us a challenge: to write the shortest C/C++ program to determine if a number is even or odd.
These are the requirements:

Get a number from keyboard, at run-time (not from command line)
Output the string pari if the number is even
Output the string dispari if the number is odd
We can assume that the input is legal
We can assume that the machine has a i386 architecture
Code preprocessing is not allowed (e.g.: use #defines)
[edit after comments] The code can be considered valid if it compiles with gcc 4.x

This is the best attempt we had so far (file test.c, 50B):
main(i){scanf("%d",&i);puts("dispari"+3*(~i&1));}

Do you think we can go further?
(*): "dispari" is the italian for odd and "pari" is the italian for even

Is this for C or C++? In C++, that code is invalid. I believe in C as well.\

@LuchianGrigore, you can use both C and C++. The choice depends on the language that lets you write the shortest code. The code above compiles correctly with gcc, maybe I should add that as a requirement.

Sorry, but your best example doesn't compile with gcc 4.6.3 (Edit: it does)

@niomaster, I have the same version and it works, but not if the file extension is different than .c. Anyway, if you think that doesn't work, you could try providing your shortest working solution :).

Slight variation (untested): use return value of scanf to shorten into main(i){puts("dispari"+3*(scanf("%d",&i)&~i));}.

@Howard that works with gcc 4.6.3!

@Jack, my solution is C, yours could be C++, hence the tag. We are not interested in warnings here, this is just a stupid competition between too nerdish colleagues!

@VincenzoPii: Ok. Removed comment. I'm sorry, I'm in the sense of stackoverflow.com.

You can't legally and portably perform output without either #include <stdio.h> (which is a preprocessor directive) or your own declaration of the routines you're using. As of C90, calling an undeclared function has defined behavior only in narrow circumstances; as of C99, it's a constraint violation (C's version of "illegal").

Why no other languages allowed?! I like Perl so much ._. print<><0?dis:$,,pari

39 bytes
Given you didn't specified the range of the number input, then here's a solution that handles 0..9 only:
main(){puts("dispari"-~getchar()%2*3);}

47 bytes (2 less)
main(i){scanf("%d",&i);puts("dispari"-~i%2*3);}

For a positive i, ~i is negative, so ~i%2 is 0 or -1.

48 bytes
main(i){scanf("%d",&i);puts("dispari"+3-i%2*3);}

34 bytes
Build with
gcc -nostartfiles -Wl,-ea odd.c
Works in GCC 6.3.0.
a(){puts("dispari"-~getch()%2*3);}


text:
Determine number of connected components
You are given a graph represented through an adjacency list. For example, the input
1-2 2-3 3-4 4-1

would correspond to the graph with nodes 1, 2, 3 and 4, where 1 is connected to 2, 2 is connected to 3, 3 is connected to 4, and 4 is connected to 1 (forming a square).
The task is to determine the number of of connected components of the graph represented by an inputted adjacency list. A "connected component" is a set of nodes from which there is no path to any other node that is not in the set.
Example:

Intput: 1-2 2-3 4-5
  Output: 2

Language of your choice - shortest code possible.

Does the input consist only of pairs of positive integers divided by a dash? The line "a lone node with no connections would be considered an unconnected component." would suggest otherwise.

@shiona Good point, I deleted that line. No lone nodes!

Usually, these would be called connected components.

Ruby, 77 characters
gets;0while$_.sub!(/\b(\d+)\b(.*) (\1-\d+|\d+-\1)\b/,'\3\2');p$_.count(" ")+1

A first plain attempt in Ruby. It collects the sub-graphs using a regular expression until no more connections can be made.
Examples:
> 1-2 2-3 3-4 4-1
1

> 1-2 2-3 4-5
2

> 1-2 3-4 8-9 1-6 5-7 7-4 10-9
3

Mathematica 126
With x holding the input string,
t = ToExpression;
Length@ConnectedComponents@Graph[Characters /@ ImportString[x, "Table"][[1]] /.
{a_, "-", b_} :>   UndirectedEdge[t@a, t@b]]

If x is input instead as a list of undirected edges, in standard Mathematica format, the solution can be reduced to 34 chars:
Length@ConnectedComponents@Graph@i

Example:

Sage, 77
len(Graph([t.split('-')for t in raw_input().split()]).connected_components())

Golfscript, 67 62 characters
This can probably be golfed down a little more but...
" "/{"-"/{~}%}%0\{.}{(:^;{.{^&},.{+}*}{.@\-\{+}*:^;}while\)\}while;
'-'%{~}%2/0\{.}{(:^;{.{^&},.{+}*}{.@\-\{+}*:^;}while\)\}while;

Important note: this ONLY works on the ruby interpreter for golfscript (from golfscript.com), NOT on the online golfscript app, because the online app incorrectly handles nested while loops. Here's the commented code:
" "/{"-"/{~}%}%   # parse into array of number pairs
'-'%{~}%2/        # parse into array of number pairs
0\                # push the counter under the current set
{.}               # copy top for the condition pop
{
    (:^;          # grab leftmost pair
  {
    .{^&},        # grab any matching the left pair, make a copy for the
    .{+}*         # condition, and merge the copy's elements together
  }{
    .@\-\         # remove the matches from remaining set
    {+}*:^;       # merge matches together & assign to '^'
  }while
  \)\             # update the counter underneath
}while;