How to test primality in O(1)

[helios]

This is "programming meets theoretical physics":

bool isprime(ulong n){
    channel c;
    ulong n2=sqrt(n),
        a;
    if (!receive(c,a))
        sendBack(c,2);
    else{
        if (a>n2)
            return 1;
        if (!(n%a))
            return 0;
        sendBack(c,a+1);
    }
    return 0;
}

Depending on the nature of the universe, this is either a deterministic test or a probabilistic test that gives false negatives.

[Duthomhas]

Except that sqrt() isn't O(1)...

Of course, I've almost got my lightsaber working... I just need to finish putting up a few more lightning rods to get enough power for the first test.

;-]

[helios]

Well, we can always make n2=n-1. That's not a problem.

Earlier today, I was talking with a friend about the possibility of writing a language that could simulate this. It would work by running virtual "threads" (it's kind of a misnomer since they wouldn't run concurrently) which would be forked (that is, paused, duplicated, and resumed) or rejoined (stopped and destroyed) accordingly when there were calls to the API functions. In other words, it creates parallel universes to run programs.
I find it too tempting not to try.

[tition]

I think current primality tests do run in parallel

[firedraco]

Don't think they run in parallel *universes* though...go go quantum computers!

[S6k9GNh0]

*Fetches Chubaka costume*
What is the point of this thread again?