Can a complex number be prime? I've been pondering over this question since a very long time. 
If a complex number can be prime then which parts of the complex number needs to be prime for the whole complex number to be prime. 
 A: Yes, a complex number can be prime (in the traditional sense of the word). Recall that $\mathbb R \subseteq \mathbb C.$ Therefore, all numbers that you would traditionally think of as being prime are themselves complex (though not non-real). So in this case, we require of $a+bi$ that $a$ be prime (in the traditional sense) and $b=0.$
However, there is the notion of being Gaussian prime. A Gaussian prime is a Gaussian integer (a complex number $a+bi$ such that $a,b\in\mathbb Z$) satisfying one of the following:


*

*If $a,b\neq 0,$ then $a+bi$ is Gaussian prime iff $a^2+b^2$ is (traditionally) prime;

*If $a=0,$ then $bi$ is Gaussian prime iff $|b|$ is (traditionally) prime and $|b|\equiv 3 \pmod 4;$

*If $b=0,$ then $a$ is Gaussian prime iff $|a|$ is (traditionally) prime and $|a|\equiv 3 \pmod 4.$
A: The notion of being "prime" is only meaningful relative to a base ring.
For instance, in the integers $\mathbb{Z}$ the number 5 is prime, whereas in the Gaussian integers $\mathbb{Z}[i]$ we have
$$5 = (2 + i)(2 - i) = 2^2 - i^2 = 4 - (-1) = 5$$
and in the ring $\mathbb{Z}[\sqrt{5}]$ we have
$$5 = (\sqrt{5})^2$$
so over these rings 5 is not a prime number.
The definition of prime you're probably familiar with -- a number is prime if it is divisible only by itself and one -- doesn't even really work over the integers: for instance, 5 is divisible not only by 1 and 5, but also by -1 and -5.  So we need to formulate the definition of a prime differently, while still preserving the basic idea, to make sense of it in an arbitary ring.
Notice the following difference between primes and composites: since 5 is prime, if we have two numbers $a$ and $b$ such that $ab$ is a multiple of 5, then obviously one of $a$ or $b$ has to be a multiple of 5 just by unique factorization.  On the other hand, if $ab$ is a multiple of 15, it may be the case that neither $a$ nor $b$ is a multiple of 15, because we might instead have $a$ a multiple of 3 but not 5 and $b$ a multiple of 5 and not 3. †
This gives us our definition of "prime" for a general ring: a ring element is prime if it is neither zero nor a unit, and moreover has the property that whenever it divides a product it must divide at least one of the factors.
There are a great many rings contained in the complex numbers, and in many of these rings there are non-real complex numbers that are primes in that ring.  However, given any number that's prime in a given ring, there's a larger ring in which it's not prime, just as we saw above that 5 is prime over the integers, but not over the Gaussian integers $\mathbb{Z}[i]$ or over $\mathbb{Z}[\sqrt{5}]$.
In particular, since $\mathbb{C}$ is a field, every nonzero element is a unit, so nothing is prime over the complex numbers.  (Similarly, nothing is prime over the real numbers, or the rational numbers.)  However, I reiterate that many complex numbers are prime over smaller rings: for instance, it turns out that $2 + i$ is prime over $\mathbb{Z}[i]$.

† A slightly more straightforward generalization of the definition you're used to would be to look at nonzero, nonunit elements $r$ for which we only have $r = s t$ when either $s$ or $t$ is a unit.  This actually gives a weaker notion called "irreducibility."  In Unique Factorization Domains the two notions are the same (which explains why they're the same for the integers), but in rings like $\mathbb{Z}[\sqrt{-5}]$ where we do not have unique factorization you can have situations like
$$3 \cdot 3 = 9 = (2 + \sqrt{-5})(2 - \sqrt{-5})$$
Here each of $3$, $2 + \sqrt{-5}$, and $2 - \sqrt{-5}$ is irreducible, with none dividing any of the others.  We've decided that being "prime" is about unique prime factorization, so we chose a definition of "prime" under which each of the above is "irreducible" but none is "prime."

Note: several answers (including this one) have brought up the Gaussian integers specifically.  They're indeed an example of a subring of the complex numbers containing non-real complex numbers, but just to be clear they're in no way "the" natural example here -- they're on the same footing as all the others.
A: As with real numbers, you can factor any complex number $z$ as $2\times\dfrac z 2$.  For example, $31$ can be factored as $2\times\dfrac{31}2$.  However, in defining prime numbers one is not working within the set of all real numbers, but within the set $\{1,2,3,\ldots\}$. (And when Euclid wrote about prime numbers in the third century BC, he did not consider $1$ to be a number.)
Mathematicians sometimes work within the set $\mathbb Z= \{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$, and then $(-3)\times(-2)=6$ is not considered to be a different factorization from $3\times2=6$, because you can change $3$ to $-3$ by multiplying it by a "unit", in this case by $-1$.  There are two "units" in $\mathbb Z$, namely $\pm1$, and the thing that qualifies them as "units" is that they are divisors of $1$.
Mathematicians also work with "Gaussian integers", which are complex numbers of the form $a+bi$ where $a,b\in\mathbb Z$, i.e. $a,b$ are ordinary integers. Within the Gaussian integers, numbers that cannot be factored are "Gaussian primes".  The number $5$ is not a Gaussian prime because $5=(2+i)(2-i)$.  It is also $(1+2i)(1-2i)$, but that is not a different factorization because $1+2i$ can be reached from $2-i$ by multiplying it by a unit, namely $-i$, since $(1+2i)(-i) = 2+i$.
A: The concept of primality is extended to other systems, including the Gaussian integers, as irreducibility. An irreducible element is one which cannot be written as the product of non-unit elements; compare this with the definition of a prime.
This is similar in principle, but can have (initially) unexpected consequences. For example, the decomposition of natural numbers into primes is unique, but the decomposition of some of those same numbers into irreducible complex numbers is not!
A: If you are thinking of Gaussian primes, $a+bi$ can be prime with neither $a$ nor $b$ prime. The simplest example is $1+i$. More complicated  is $4+15i$. Here I used the fact that if $a^2+b^2$ is an ordinary prime, then $a+bi$ is a Gaussian prime.
A: The analogous concept would be to consider the Gaussian integers $g = m + ni : m,n \in \Bbb{Z}$ and say that $g$ is prime if there is no pair of Gaussian integers such that $ hk = g; |h| \neq 1; |k|\neq 1$. 
So for example, in the field of Gaussian integers, $5 = (2+i)(2-i)$ is not prime.
Two caveats here:
(1) There is no simple way to tell of $g$ is prime, based on whether its real and imaginary parts are prime.  
(2) The Gaussian Integers are not a unique factorization domain; that is, a number can have two non-trivially distinct factorizations.  The latter property is very likely the place where Fermat's "too big for the margin" proof was flawed, because there is indeed a very clever (maybe remarkable) proof of his last theorem that uses numbers of this form and assumes unique factorization.
A: A prime is an integer $p>1$ that cannot be written as $p=ab$ where $a,b>1$ are integers. Clearly, any prime in this sense is also a complex number (since $\mathbb{N}\subset\mathbb{C}$).
More abstractly, an element $p$ of a commutative ring is prime if it is nonzero, noninvertible (i.e. not a unit), and satisfies the condition
$$
p\mid ab\implies p\mid a\text{ or }p\mid b.
$$
You can check that this is consistent with our original definition in $\mathbb{N}$.
David points out an example in $\mathbb{Z}[i]$.
