This works for any sides which are odd integers (no need to be prime), provided it is a valid triangle, whether acute or obtuse.  Let a,b,c be any integers.

Call sides 2a+1, 2b+1, 2c+1

Assuming this makes a valid triangle and therefore Heron's Formula is valid:

The semiperimeter = (2a+2b+2c+3)/2

A^2 = (1/16)(2a+2b+2c+3)(2a+2b-2c+1)(2a-2b+2c+1)(-2a+2b+2c+1)

This numerator expands to (thank you Wolfram Alpha)

-16 a^4 - 32 a^3 + 32 a^2 b^2 + 32 a^2 b + 32 a^2 c^2 + 32 a^2 c - 8 a^2 + 32 a b^2 + 32 a b + 32 a c^2 + 32 a c + 8 a - 16 b^4 - 32 b^3 + 32 b^2 c^2 + 32 b^2 c - 8 b^2 + 32 b c^2 + 32 b c + 8 b - 16 c^4 - 32 c^3 - 8 c^2 + 8 c + 3

All of the terms with coefficients of 16 or 32 will be integers after being divided by 16.  So let's take them out and see what is left:

8(a-a^2) + 8(b-b^2) + 8(b-b^2) + 3

Whether a is odd or even, a-a^2 is always even because squaring maintains the same parity.

So every term except for the 3 is divisible by 16.

A^2 = An integer + 3/16